基于异或运算的机会网络高效转发策略*

2014-09-13陈志刚曾剑锋

计算机工程与科学 2014年11期

关键词：队列路由机会

刘辉，陈志刚，吴嘉，王丹，曾剑锋

(1．中南大学软件学院，湖南长沙 410075；2．“移动医疗”教育部-中国移动联合实验室，湖南长沙 410083)

基于异或运算的机会网络高效转发策略*

刘辉1,2，陈志刚1,2，吴嘉1,2，王丹1,2，曾剑锋1

(1．中南大学软件学院，湖南长沙 410075；2．“移动医疗”教育部-中国移动联合实验室，湖南长沙 410083)

通过对机会网络中节点传递信息的方式进行研究分析，遍历可以通信的邻居节点，将两节点的信息作比较。通过交集的形式，选择节点中携带信息异或程度最大的邻居节点作为下一跳进行信息传递，从而形成一条有效性最大的通信路径。基于这样的分析过程，提出了一种基于异或运算的机会网络高效转发策略FSXO。通过与机会网络中的经典算法对比，仿真结果表明，FSXO策略能够在高传输成功率的情况下，减少网络中无效数据副本的存在，从而有效地降低路由开销，减少资源的消耗。

机会网络；异或运算；通信路径；转发策略

1 引言

机会网络是不需要源节点和目标节点之间存在完整链路，利用节点移动带来的相遇机会实现通信的、时延和分裂可容忍的自组织网络[1]。机会网络来源于早期的延迟容忍网络DTN(Delay Tolerant Network)[2]，机会网络可以看成是具有一般DTN网络特征的无线自组网。在机会网络中，节点的位置不是固定的，网络的规模也未进行设置，源节点和目标节点之间的路径事先不能确定是否存在。

机会网络是利用节点移动而形成的通信机会逐跳进行消息的传输，以“存储—携带—转发”的路由模式实现节点间的通信，由于其固有的特点能够满足某些特定应用的需求[3]。目前，机会网络的应用主要在深太空信息网[4]、野外数据收集[5]和灾难场景应用[6]等领域，取得了较好的成果。

2 相关工作

在机会网络中，信息转发是指信息由源节点经过单跳或者多跳转发到目的节点的过程，如何有效地进行信息转发是机会网络研究的一个热点。

Direct Transmission算法[7]是基于转发策略的路由算法，该算法的特点是数据分组在转发过程中，节点不会对其进行复制，只有源节点遇到目的节点时才会进行数据分组转发。因此，在整个网络中不存在多余的数据副本，网络路由开销最小，但传输延迟较大，传输成功率不高。

Li Y等人在文献[8]中提出了Epidemic算法，它的核心思想是当两个节点可以通信时，在获知对方携带的数据分组情况后，仅传送对方没有的数据分组。理论上经过多次交换后，每个非孤立节点都将获得所有数据分组，从而实现数据传输。在网络带宽、节点缓存和节点能量等网络资源丰富时，可以减少传输延迟，保证最大化数据传输的成功率。然而在实际应用中，网络资源是有限的，随着节点数目的增多，网络中会存在大量的无用数据副本，消耗过多的网络资源，从而导致网络性能下降。

Huang W等人在文献[9]中提到，Spray and Wait算法分为Spray阶段和Wait阶段。在Spray阶段，源节点的每个数据分组向网络中注入一定数目的数据副本，并将其转发给周围节点。在Wait阶段，如果数据在Spray阶段没有传送到目标节点，那么携带数据的节点将通过Direct Transmission方式把数据传送到目标节点。通过这种策略限定了网络中的数据分组副本数量从而避免泛洪。该算法和其他路由算法综合比较有明显的优势。

PRoPHET算法[10]是基于概率计算策略的。当两个节点可以通信时，首先估算各自成功传输的概率，利用该值来决定是否进行数据分组转发。在社区模型仿真场景中，该算法的性能较好。但是，在实际应用中常常存在无法预测的问题，导致算法效率变低，影响该算法的效果。

通过对上述算法的研究分析，本文提出了一种基于异或运算的机会网络高效转发策略FSXO(Forwarding Strategy based on XOR Operation)。在该算法下，相邻节点间通过携带信息的比较，选择节点中携带信息异或程度最大的邻居节点作为下一跳进行信息传递，从而形成一条有效性最大的通信路径，从而更有可能将信息传递到其他通信区域，实现通信。

3 基于异或运算的机会网络高效转发策略

3.1 机会网络结构

机会网络的特点是节点只有在同一连通区域内才可以相互传递信息，而不在同一连通区域的节点只有通过节点的移动才能实现信息的传递。在某个时段内，整个网络被划分为多个连通域，机会网络结构图如图1所示。在灰色区域内的节点可以相互通信，从而实现网络数据传输，但是不能将信息传递到整个网络，只有通过活动节点的移动才能将本身携带的信息传递到其他区域。

由图1可知，在T时间内，A节点的数据只可以传输给D、E节点，而另一区域的B、C节点将无法获得数据。只有通过A、D、E节点的移动，才有可能将数据传递到另外区域。因此，在某一连通区域如何选择节点，使得节点携带的信息量更多，从而更有可能传送到其他区域将是本文的主要研究工作。

Figure 1 Structure of opportunistic network图1 机会网络结构图

3.2 子网络拓扑结构图

根据上述机会网络特点，在网络中任意选择某一个子网络作为研究的对象。在T时段，任选一个子网络，假设该子网络包含的节点集合为V={A,B,C,D,E,F,M,H,K,L}，所有参与的节点都为中继节点，实现消息的转发，子网络节点图如图2所示。

假设当前时段由A节点发送信息，并且信息传递速度大于节点移动速度，则当前时段里子网络的拓扑结构不发生变化，A节点的信息可以传递到子网络的所有节点。根据节点和邻接点的关系构建当前子网络的拓扑结构有向图，如图3所示。

Figure 2 Nodes of sub-network图2 子网络节点图

Figure 3 Topology structure of sub-network图3 子网络拓扑结构图

根据网络的拓扑结构，我们得到有向图G=(V，E)，其中V={A,B,C,D,E,F,M,H,K,L}，E={〈A，B〉，〈A，C〉，〈A，D〉，〈B，E〉，〈B，F〉，〈C，M〉，〈D，H〉，〈F，K〉，〈F，L〉}。通过有向图可以看到可能的信息传递路径。此时，需要找的是一条有效性最大的通信路径，将它作为最终的信息传递路径，使得信息经过多跳传递后的终节点携带的信息量最大，从而更有可能将信息传递出去，实现通信。

3.3 节点信息遍历过程

每个节点维护一个缓冲区，缓冲区中存放本节点和其他节点需要本节点转发的数据分组，每个数据分组有一个全局唯一的标识。令节点集合V中的每个节点数据分组分别为DA={a，b}，DB={c，d，e}，DC={f，g}，DD={a，c}，DE={x，y}，DF={h，i}，DM={a，x}，DH={x，y，z}，DK={j，k，l，m}，DL={p，q，y}。添加了数据分组的子网络拓扑结构有向图如图4所示。

Figure 4 Topology structure of sub-network with data图4 子网络拓扑结构有向图(带数据)

为了获得最优化路径节点集合，令集合V中每个节点各自形成一个只含本身节点的子集合，记作VA={A}，VB={B}，VC={C}，VD={D}，VE={E}，VF={F}，VM={M}，VH={H}，VK={K}，VL={L}。为了确定最优路径，将采用广度优先搜索(BFS)遍历有向图G中的节点。

基于图4的算法具体执行过程如下：

(1)初始时，Queue队列只有A节点一个元素，将该元素出队列，即A节点为当前节点，访问A节点的第一个邻接点B，此时VA中只有A一个元素，作如下运算：

IntersectionAB=DA∩DB

IntersectionAB集合为空，则表明当前两个节点所携带的信息是不一样的，将B节点插入到Queue队列中，并将VA中的元素加入到VB中。

(2)继续访问A节点的下一个邻接点C，作如下运算：

IntersectionAC=DA∩DC

IntersectionAC集合也为空，将C节点插入到Queue队列中，并将VA中的元素加入到VC中。

(3)继续访问A节点的下一个邻接点D，作如下运算：

IntersectionAD=DA∩DD

IntersectionAD集合不为空，则表明信息存在冗余，不执行其他操作。

(4)当前节点A没有邻接点，则将Queue队列队首元素B出队列，访问节点B的邻接点E，VB中此时有两个元素A和B，作如下运算：

IntersectionABE= DA∩DB∩DE

IntersectionABE集合为空，将E节点插入到Queue队列中，并将VB中的元素加入到VE中。

(5)继续访问B节点的下一个邻接点F，作如下运算：

IntersectionABF= DA∩DB∩DF

IntersectionABF集合为空，将F节点插入到Queue队列中，并将VB中的元素加入到VF中。

(6)当前节点B没有邻接点，则将Queue队列队首元素C出队列，访问节点C的邻接点M，VC中此时有两个元素A和C，作如下运算：

IntersectionACM= DA∩DC∩DM

IntersectionACM集合不为空，则不执行其他操作。

(7)当前节点C没有邻接点，则将Queue队列队首元素E出队列，E节点没有邻接点，继续将Queue队列队首元素F出队列，访问节点F的邻接点K，VF中此时有三个元素A、B和F，作如下运算：

IntersectionABFK=DA∩DB∩DF∩DK

IntersectionABFK集合为空，将K节点插入到Queue队列中，并将VF中的元素加入到VK中。

(8)继续访问F节点的下一个邻接点L，作如下运算：

IntersectionABFL=DA∩DB∩DF∩DL

IntersectionABFL集合为空，将L节点插入到Queue队列中，并将VF中的元素加入到VL中。

(9)当前节点F没有邻接点，则将Queue队列队首元素K出队列，K节点没有邻接点，继续将Queue队列队首元素L出队列，L节点也没有邻接点，此时Queue队列为空，访问结束。

(10)统计节点个数不为1的集合的信息量，知VK集合中有A、B、F、K四个元素，其元素对应的数据分组集合信息量总和最大，将ABFK设为最优，消息通过复制策略在路径A→B→F→K进行传递。

3.4 算法设计

根据前一节的遍历过程可知FSXO算法执行过程如下：

(1)队列Queue初始值存放发送信息的第一个节点，将队首元素出队列作为当前节点i。

(2)根据BFS访问当前节点i的邻接点j，将Dj与Vi集合中的所有元素对应的数据分组集合同时做交操作，即如下运算：

Intersectionij=Dj∩Di1∩…∩Din

(1)

其中，n为Vi集合的元素个数，Di1到Din为Vi集合元素对应的数据分组集合。

(3)如果Intersectionij集合为空，则将节点j插入到Queue队列尾部，并将节点i对应的Vi集合的所有元素加入到Vj中，否则不执行任何操作，转到(4)。

(4)继续访问当前节点i其他邻接点，重复(2)和(3)，直到其所有邻接点访问完毕。

(5)将队列的队首节点出队列，作为当前节点i，重复(2)、(3)、(4)，直至队列为空。

(6)统计节点个数不为1的集合的信息量，信息量最大的集合则为最优路径的节点集合，从而确定信息传递路径，将消息通过复制策略在该路径上传递。

根据上述选择的过程，可以得到基于异或运算的机会网络高效路由算法，如下所示。

算法1AnEfficientForwardingStrategybasedonXOROperation

1:Input:AgraphG(V,E),asourceS, Dα:thecorrelativeinformationcollectionofα(α∈ V);

2:Output:Apathofthemaximuminformation。

3:Init:InitQueue(Q),Vi/*eachelementofVasanodecollection*/

4:Set:EnQueue(Q,S);

5:while(!QueueEmpty(Q))

6:DeQueue(Q,β);

7:for(k=FirstAdjVex(G,β);k>=0;k=NextAdjVex(G,β,k))

8:nis the number of element ofVβ,Dα1,…,Dαnare the correlativeinformation collection of element ofVβ;

9:IntersectionβK=DK∩Dα1∩…∩Dαn;

10:if(IntersectionβK=∅)

11:EnQueue(Q,k);

12:add all element ofVβto the collectionVK;

13:end if; end for; end while

14:select a maximum information collection ofVithat the number of elements inViis greater than one;

15:according to the above collection generate a path;

通过上述的选择操作，可以避免网络中存在大量的数据分组副本，从而避免消耗大量的网络资源。

4 实验仿真与结果分析

本文将采用ONE(Opportunistic Networking Environment)[11]仿真工具,并与经典的Epidemic算法和PRoPHET算法在仿真平台上进行比较。将选用传输成功率、传输延迟和路由开销这三个指标对算法进行比较分析。仿真场景设置如表1所示。

Table 1 Parameters of simulation表1 仿真场景的参数

下面是Epidemic算法、PRoPHET算法和FSXO算法在不同节点密度下的表现。图5为不同节点密度下三种算法传输成功率的实验结果。

Figure 5 Delivery ratio图5 传输成功率

由图5可知，节点密度对算法传输成功率有较大的影响。在节点较少的情况下，三种算法的传输成功率差不多。随着节点数目的增加，各个算法的传输成功率都有所增加，但是FSXO算法增加幅度比其他两种算法的高。在节点数量到达400时，Epidemic算法和PRoPHET算法的传输成功率保持在40%左右，而FSXO算法的传输成功率却可以达到70%左右，其根本原因在于FSXO算法构建网络拓扑图，通过异或操作选择出了一条信息量大的通信路径进行信息传递。正是这种有选择性的信息传递使得其在仿真平台下能够取得较高的信息传输成功率。

节点数量对传输延迟的影响如图6所示。由图6可知，节点数量对三种算法的传输延迟影响都不大。Epidemic算法的传输延迟要优于FSXO算法和PRoPHET算法，这是因为Epidemic算法本质上是一种洪泛算法，它能够减少传输延迟，而其它两种算法是基于某种选择性的算法，使得一些节点不能参与通信而造成延迟。在节点数量较少时，PRoPHET算法增加的趋势比FSXO算法明显。随着节点数量增加，FSXO算法和PRoPHET算法的传输延迟非常接近。从仿真结果得出，Epidemic算法的延迟时间小于FSXO算法和PRoPHET算法的。

Figure 6 Delivery delay图6 传输延迟

节点数量对路由开销的影响如图7所示。在节点个数较少的情况下，三种算法的路由开销差不多。Epidemic算法的路由开销随着节点数量的增加而大幅度增加，增加趋势非常明显，说明该算法随着节点数量的增加网络中存在大量的数据分组副本，浪费网络资源。PRoPHET算法的路由开销也随着节点的数量增加而增加，但是增加的幅度比Epidemic算法小。就路由开销而言，PRoPHET算法要优于Epidemic算法。FSXO算法的性能明显优于前面两种算法，在节点个数达到400时，FSXO算法的路由开销还不到Epidemic算法的1/2，比PRoPHET算法也要少1/3。这是由于该算法不是将信息转发给所有遇到的节点，而是通过异或运算有选择地选择了有效性高的一串节点进行转发，从而减少网络中副本的存在。仿真结果表明，FSXO算法能够减少路由开销，节约网络资源。

Figure 7 Overhead图7 路由开销

通过对仿真实验结果的分析可知，FSXO算法能在减少路由开销的同时保证较高水平的传输成功率，减少网络中数据分组副本的数量，进而节约网络资源，提高网络的整体性能水平。不足之处在于FSXO算法会造成一定的传输延迟，但就整体性能而言，FSXO算法相对于Epidemic算法和PRoPHET算法有较大的进步。

5 结束语

针对机会网络中节点传递信息的特点，本文提出了基于信息异或的选择信息量最大的路径传递信息的算法FSXO。通过遍历可通信的邻居节点，将两节点的信息作比较。通过交集的形式，比较节点中携带信息异或程度最大的邻居节点作为下一跳进行信息传递，从而形成一条有效性最大的通信路径。通过与机会网络中经典的Epidemic算法和PRoPHET算法对比，仿真结果表明，FSXO算法能够在高传输成功率的情况下，减少网络中无效数据副本的存在，从而有效降低路由开销，这种特性使得该算法非常适合于能量资源较少的场景。

[1] Xiong Yong-ping, Sun Li-min, Niu Jian-wei, et al.Opportunistic networks[J].Journal of Software, 2009, 20 (1):124-137.(in Chinese)

[2] Jacquet P, Mans B, Rodolakis G. Information propagation speed in mobile and delay tolerant networks[J]. IEEE Transactions on Information Theory, 2010, 56(10):5001-5015.

[3] Hu Si-quan, Wang Hong-bing, Wang Jun-feng. Research on the opportunistic networks [J]. Computer Science, 2009, 36 (10):32-37.(in Chinese)

[4] Zhang L, Huang W, Miao X, et al. The impact of storage capacity usage and predictable contact schedule on dynamic routing for opportunistic deep space information networks[J]. Wireless Personal Communications, 2014,77(2):1-19.

[5] Tseng Y C, Wu F J, Lai W T. Opportunistic data collection for disconnected wireless sensor networks by mobile mules[J]. Ad Hoc Networks, 2013, 11(3):1150-1164.

[6] Martín-Campillo A, Crowcroft J, Yoneki E, et al. Evaluating opportunistic networks in disaster scenarios[J]. Journal of Network and Computer Applications, 2013, 36(2):870-880.

[7] Sun Jian-zhi, Liu Nai-rui, Zhang Ying-xin, et al.Performance analysis of typical routing algorithm in opportunistic network [J]. Computer Engineering, 2011, 37(16):86-89.(in Chinese)

[8] Li Y, Hui P, Jin D, et al. Evaluating the impact of social selfishness on the epidemic routing in delay tolerant networks[J]. IEEE Communications Letters, 2010, 14(11):1026-1028.

[9] Huang W, Zhang S, Zhou W. Spray and wait routing based on position prediction in opportunistic networks[C]∥Proc of 2011 3rd IEEE International Conference on Computer Research and Development (ICCRD), 2011:232-236.

[10] Gibran K. The PRoPHET:A new annotated edition[M]. London:Oneworld Publications, 2012.

[11] Keränen A, Ott J, Kärkkäinen T. The ONE simulator for DTN protocol evaluation[C]∥Proc of the 2nd International Conference on Simulation Tools and Techniques, 2009:55.

附中文参考文献：

[1] 熊永平，孙利民，牛建伟,等. 机会网络[J]. 软件学报, 2009, 20(1):124-137.

[3] 胡四泉，汪红兵，王俊峰. 机会型网络研究综述[J]. 计算机科学, 2009, 36(10):32-37.

[7] 孙践知，刘乃瑞，张迎新,等. 机会网络典型路由算法性能分析[J]. 计算机工程, 2011, 37(16):86-89.

LIUHui,born in 1989,MS candidate,his research interest includes opportunistic network.

陈志刚(1964),男,湖南益阳人，博士，教授，CCF会员(E200005226S)，研究方向为网络与分布式计算。E-mail:czg@csu.edu.cn

CHENZhi-gang,born in 1964,PhD,professor,CCF member(E200005226S),his research interests include wireless networks, and distributed computing.

吴嘉(1983),男,贵州贵阳人，博士生，CCF会员(E200039369M)，研究方向为机会网络和软件工程。E-mail:jiawu5110@163.com

WUJia,born in 1983,PhD candidate,CCF member(E200039369M),his research interests include opportunistic network, and software engineering.

王丹(1989),女,河北保定人，硕士生，研究方向为机会网络。E-mail:csuwangdan@163.com

WANGDan,born in 1989,MS candidate,her research interest includes opportunistic network.

曾剑锋(1988),男，湖南邵阳人，硕士生，研究方向为机会网络。E-mail:zjf19881202@163.com

ZENGJian-feng,born in 1988,MS candidate,his research interest includes opportunistic network.

AnefficientforwardingstrategybasedonXORoperationinopportunisticnetwork

LIU Hui1,2，CHEN Zhi-gang1,2，WU Jia1,2，WANG Dan1,2，ZENG Jian-feng1

(1.School of Software,Central South University,Changsha 410075;2. “Mobile Health” Ministry of Education-China Mobile Joint Laboratory,Changsha 410083,China)

Through studying the ways of forwarding information in opportunistic networks,the communication nodes in the neighbourbood can be traversed and the two nodes can be compared.Through the form of the intersection,the neighbor node with the largest XOR is chosen as the next hop to transfer the information so that a communication path with maximum effectiveness is formed. Based on this analysis process, an efficient forwarding strategy based on XOR operation in opportunistic networks (FSXO) is proposed.The proposal is compared with classical algorithms in opportunistic networks,and the simulation results show that the proposed FSXO strategy can reduce the presence of invalid copy data at high transmission rates,thus effectively reduce the routing overhead and resource consumption.

opportunistic network;XOR operation;communication path;forwarding strategy

1007-130X(2014)11-2094-06

2014-06-06;

：2014-08-20

国家自然科学基金资助项目(61073186，61379057，61309001，61379110, 61103202)；教育部博士点基金优先发展领域课题资助项目(20120162130008)；国家973计划资助项目(2014CB046305)；教育部博士点基金新教师类资助项目(20110162120046)

TP391.02

：A

10.3969/j.issn.1007-130X.2014.11.007