2. 重庆师范大学 计算机与信息科学学院, 重庆 400047
根据机会网络中节点较稳定的社会属性，提出了一种兴趣社区检测机制，将机会网络中节点的兴趣爱好量化，根据节点间兴趣爱好相似性进行兴趣社区划分.利用节点在运动过程中形成的社区，综合考虑节点的社区属性和节点间历史接触信息，设计了兴趣社区路由算法.兴趣社区路由由社区内路由和社区间路由组成，路由机制是选择与目标节点在同一兴趣社区且与目标节点接触较多的节点作为中继节点完成数据包转发.通过仿真实验验证兴趣社区路由策略的合理性和有效性.仿真结果表明，所提出的兴趣社区路由算法能有效降低网络开销和时延，提高了投递率.
2. College of Computer and Information Science, Chongqing Normal University, Chongqing 400047, China
As a result of relative stability of social relations between people in opportunistic networks, an interest community detecting method is proposed by quantifying the interests of nodes and comparing the similarity with the interest properties of nodes. Utilizing the communities generated by moving nodes and comprehensively considering the community property of nodes and the contact information among nodes, an interest community routing (ICR) scheme is presented. The ICR scheme is divided into two parts: routing within the community and routing among communities. The nodes which in the same community and contact more frequently with the destination node will be chosen as relay nodes. Simulations demonstrate the rationality and effectiveness of ICR, and shows that ICR can efficiently reduce the average overhead ratio and decrease delivery delay and increase the delivery ratio.
机会网络(ON, opportunistic networks)[1]是一种源节点和目的节点之间不需要保持完整的通信链路，利用节点移动所带来的机会来实现消息传输的自组织网络.现有的无线网络路由算法[2]多是基于端到端之间有可靠连接这一前提，已不适用于机会网络.实际的机会网络应用场景主要由人、汽车及其他交通工具携带的移动设备组成，网络主要以人为载体，人们之间相互联系会形成许多社会关系，与节点运动速度快、网路拓扑结构变化快的特性不同，节点间的社会关系较为稳定且彼此存在一定依赖性，有一定的规律可循[3].大量文献表明，利用节点的社会属性来设计机会网络路由协议是行之有效的方法，能获得较好网络性能[4]. Bulut等[5]利用社会网络理论中“朋友”的概念，设计出一种机会网络数据传输策略，如何合理度量“朋友”这一特性并将其有效检测出来是该方法的最大挑战. Pan等[3]提出了基于社区的消息传输算法，采用的是一种类似冒泡的思想. Thomas等[6]提出了利用社区结构促进转发效率的协议.笔者从研究节点的社会属性出发，提出一种基于节点兴趣的兴趣社区检测策略.结合节点的社区性质和节点间的距离限制，设计出一种机会网络兴趣社区路由(ICR, interest community routing)协议.
1 兴趣社区检测策略在实际网络环境中，用户会对不同的信息产生不同的偏好，具有共同兴趣爱好的用户更愿意与彼此分享交流偏好的信息，相遇几率较大[7].基于这一现象，提出一种兴趣社区划分策略.
1.1 定义与度量节点兴趣爱好属性向量：假设全网存在n种类型的消息，通过定义一个n维兴趣爱好属性向量来度量节点对不同消息的偏爱程度.
|
(1) |
其中：Inodek表示节点k的兴趣爱好属性，dmi表示节点k对第i种信息感兴趣的程度，为了不失一般性，它的值必须满足：1) 
消息属性向量：定义一个n维消息属性向量来表示消息的类型，其定义方式为
|
(2) |
其中：Hmsgk表示消息k的消息属性，pmi表示消息k属于mi这种数据类型的概率，它必须满足：1) 
节点相似性：现有两个n维向量A、B分别表示节点i与j的兴趣爱好属性.当两个节点进入彼此的通信范围时，通过比较彼此间兴趣爱好属性，即可得到网络中任意两节点的兴趣爱好的相似性，节点相似性可通过余弦相似性公式计算得出
|
(3) |
其中：‖X‖表示向量X的模，两节点的相似性越高，则说明节点间共同的兴趣越多，彼此间交流越频繁.
1.2 兴趣社区划分假设网络中存在n种不同类型的消息，由m1, …，mi, …, mn表示，网络中的节点将自己的兴趣爱好量化存储在本地缓存，且各类消息将消息属性加入消息头部.对于消息mi，将其消息属性向量中pmi值设为1，其余值设为0.在单位时间间隔内，向网络中的节点广播某一类消息，例如在广播消息mi的期间，当节点k接收到mi时，节点运用式(3) 计算自己兴趣爱好属性与mi的消息属性间的相似性，并将值其保存到本地缓存中.当网络中n种消息全部广播到网络中每一个节点时，节点k保存了n个相似性值，如果在这n个值中，最大值的个数为1，且其值为sim(nodek, mi)，表示节点k对消息最mi感兴趣，将其加入到i社区.如果最大值的个数为h(h＞1)，则该节点属于多个兴趣社区，将其加入相应社区里去.网络中存在n种不同类型的消息，则对应存在n个兴趣社区.由于用户的兴趣并不单一，他可能对2种或多种信息有着相同的偏爱程度，所以，节点可属于多个社区.每个节点都有一个社区标签来标明自己所属兴趣社区，该社区标签被定义为一个n维向量：
|
(4) |
其中：Cid, nodek是节点k的社区标签，cmi表示节点k是否属于兴趣社区i，当cmi=1时，表示节点k属于兴趣社区i，而cmi=0则表示节点不属于兴趣社区i.
2 基于兴趣社区的路由策略在同一兴趣的节点地理位置可能相距甚远，消息传输时延较大.如果2个节点的地理位置相距较近，它们接触更为频繁.通过定义节点接触次数来判断节点间的物理距离.定义节点相似性表来记录节点间的兴趣爱好相似性.其具体形式如表 1、表 2所示.
|
表 1 节点接触信息表 |
|
|
表 2 节点相似性表 |
其中：nodekID表示节点k的ID号，nodeiID是节点i的ID号，num(nodek, nodei)是节点k与节点i在截止到当前时刻的历史接触次数. sim(nodek, nodei)是节点k与节点i的兴趣相似度.
2.1 社区内路由策略当源节点与目标节点在同一兴趣社区时，节点将实施社区内路由策略，其具体步骤如下：
步骤1 网络节点初始化，节点设置自己的兴趣爱好属性向量及兴趣社区标签；
步骤2 节点相遇之后，交换彼此的兴趣爱好属性向量和社区标签，更新节点本地接触信息表中历史接触次数，若节点之间为首次相遇，则将接触节点信息添加至接触信息表，同时，计算出节点间相似性值，更新彼此相似性表；
步骤3 当某节点S产生一个以节点D为目的节点的消息时，节点S将该消息的消息属性设为目标节点的兴趣爱好属性向量，在其运动周期内的某一时刻t，有k个节点(用节点集Nk表示)进入节点S的通信范围内，首先判断Nk中是否存在节点D，若存在，则直接将数据包传给该节点；若不存在，则跳至步骤4；
步骤4 查询Nk中每个节点与节点S的兴趣社区Cid，有m个节点(用节点集Nm表示)与节点S在同一社区.若m=0，消息将不被转发给任何一个相遇节点；若m＞0时，分别查看节点S与节点i(nodei∈Nm)的接触信息表，若num(nodei, nodeD)＜num(nodeS, nodeD)，消息将不会传给节点i；若num(nodei, nodeD)＞num(nodeS, nodeD)，且在Nm中有h(h≥2) 个节点满足该条件，则跳至步骤5；如果0＜h＜2，则直接将消息传给满足条件的节点，当num(nodei, nodeD)=num(nodeS, nodeD)，则跳至步骤6；
步骤5 当num(nodei, nodeD)＞numt(numt是可设置的阀值，numt＞num(nodeS, nodeD))时，查询节点i的相似性表，若其相似性表中包含与目标节点相似性信息，且sim(nodei, nodeD)≥simt(simt是可设置的阀值)，将节点i视作候选中继节点，若在Nm中存在j (j≥2) 个这样的候选节点，则按其与节点D的接触次数由大到小排列，将消息传送给前g(g是可设置的阀值，0＜g≤j)个候选中继节点，若0＜j＜2，则直接将消息传给满足条件的节点；
步骤6 查询节点i的相似性表，若其相似性表中包含与目标节点相似性信息，且sim(nodei, nodeD)＞sim(nodeS, nodeD)，将消息直接传给节点i；若sim(nodei, nodeD)≤sim(nodeS, nodeD)，消息将继续保留在携带节点中，直至下一相遇时机.
2.2 社区间路由策略当源节点与目标节点在不同兴趣社区时，节点实施社区间路由策略，该策略的步骤1~步骤3同社区内路由策略相同，其余步骤如下：
步骤4 查询Nk中节点与节点D的兴趣社区Cid，若有m个节点(用节点集Nm表示)与节点D在同一社区，当m＞0时，跳至步骤5；当m=0时，跳至步骤6；
步骤5 查看节点i (nodei∈Nm)的接触信息表，若num(nodei, nodeD)＞0，则将消息直接传给节点i；若num(nodei, nodeD)=0，则跳至步骤6；
步骤6 在相遇节点集Nk中，若存在j个属于多个兴趣社区的节点，若j＞0，则将消息传这j个相遇节点；若j=0，则将消息传给Nk中任意一个节点，直至下一个相遇时机.
3 仿真结果与性能分析3.1 仿真场景及参数笔者主要分析了节点缓存、消息生存时间(TTL, time to live)及网络节点个数对路由性能的影响，主要从消息投递率、网络路由开销和网络平均时延来定量分析路由算法的性能，并与机会网络经典路由机制Epidemic路由和Prophet路由进行比较.以机会网络环境(ONE，opportunistic network environment) [8]为仿真平台.通过兴趣社区划分策略将网络中节点划分到相应的社区中，选取numt=3，simt=0.6，仿真中兴趣社区为4个.
3.2 仿真结果与分析3.2.1 节点缓存对路由策略的影响节点缓存对消息投递率、路由开销及平均时延的影响如图 1~图 3所示，在图 1中，随着节点缓存增大，由于消息缓存溢出而被丢弃的概率降低，网络投递率呈递增趋势.在节点缓存空间有限时，ICR算法的消息投递率明显优于Epidemic和Prophet算法. 图 2显示了不同节点缓存下的平均网络开销，由图 2可见，节点缓存越大，则平均网络开销越小. 图 3显示随着节点缓存增加，网络延时也会随之增加.因为节点缓存越大，消息可在节点缓存中暂存时间越长.
|
图 1 不同节点缓存下的投递率 |
|
图 2 不同节点缓存下的网络开销 |
|
图 3 不同节点缓存下的平均时延 |
图 4~图 6分别体现了当TTL不同时，ICR算法在消息投递率、路由开销及平均时延性能优势. 图 4显示了消息投递率随着消息TTL的增加先增大后减小. 图 5显示了不同TTL下的平均网络开销，平均网络开销随着消息TTL的增加先减小后增大，图 5中ICR算法的平均网络开销低于Epidemic算法，略高于Prophet算法.由图 6可见，ICR算法的平均网络延时明显优于Epidemic和Prophet路由算法.
|
图 4 不同TTL下的投递率 |
|
图 5 不同TTL下的网络开销 |
|
图 6 不同TTL下的平均时延 |
网络节点数对投递率的影响如图 7所示，随着节点数增加，节点与其他节点接触的机遇越多，ICR的消息投递率呈明显上升趋势.由图 8可见，平均网络开销随着节点数增加而增大，图 8中ICR算法的平均网络开销明显低于Epidemic与Prophet算法.
|
图 7 不同节点数下的投递率 |
|
图 8 不同节点数下的网络开销 |
针对机会网络中节点对不同信息具有不同的兴趣这一社会性质出发，提出一种兴趣社区划分策略，基于节点的社区性质和接触信息，提出ICR路由策略.理论和仿真分析表明，提出的ICR路由算法能够有效地提高消息投递率，降低平均网络开销，并获得较短的平均网络延时.
| [1] |
熊永平, 孙利民, 牛建伟, 等. 机会网络[J]. 软件学报, 2009, 20(1): 124–137.
Xiong Yongping, Sun Limin, Niu Jianwei, et al. Opportunistic networks[J].Journal of Software, 2009, 20(1): 124–137. |
| [2] |
刘元安, 唐碧华, 胡月梅. Ad hoc网络中的路由算法[J]. 北京邮电大学学报, 2004, 27(2): 1–7.
Liu Yuan'an, Tang Bihua, Hu Yuemei. Routing algorithms in mobile Ad hoc networks[J].Journal of Beijing University of Posts and Telecommunications, 2004, 27(2): 1–7. |
| [3] | Pan Hui, Crowcroft J, Yoneki E. Bubble rap: social-based forwarding in delay-tolerant networks[J].Mobile Computing, IEEE Transactions on, 2011, 10(11): 1576–1589. doi: 10.1109/TMC.2010.246 |
| [4] | Zhu Ying, Xu Bin, Shi Xinghua, et al. A survey of social-based routing in delay tolerant networks: positive and negative social effects[J].Communications Surveys and Tutorials, IEEE, 2013, 15(1): 387–401. doi: 10.1109/SURV.2012.032612.00004 |
| [5] | Bulut E, Szymanski B K. Friendship based routing in delay tolerant mobile social networks[C]//Global Telecommunications Conference (GLOBECOM 2010).[S.l.]: IEEE Press, 2010: 1-5. |
| [6] | Thomas M, Phand S, Gupta A. Using group structures for efficient routing in delay tolerant networks[J].Ad Hoc Networks, 2009, 7(2): 344–362. doi: 10.1016/j.adhoc.2008.04.001 |
| [7] | Mei A, Morabito G, Santi P, et al. Social-aware stateless forwarding in pocket switched networks[C]//International Conference on Computer Communications (INFOCOM 2011).[S.l.]: IEEE Press, 2011: 251-255. |
| [8] | Keränen A, Ott J, Kärkkäinen T. The ONE simulator for DTN protocol evaluation[C]//Proceedings of the 2nd International Conference on Simulation Tools and Techniques. Rome:[s.n.], 2009: 1-10. |