基于节点差异性的机会网络数据转发算法

高彩霞，祁昌平

(河西学院信息技术与传媒学院 ,甘肃张掖 734000)

基于节点差异性的机会网络数据转发算法

高彩霞，祁昌平

(河西学院信息技术与传媒学院 ,甘肃张掖 734000)

为了提高机会网络传输成功率，降低传输开销，提出了一种基于节点差异性的机会网络数据转发算法.选择剩余能量大、邻居更新速度快的节点作为中继节点，根据节点对的邻居相似度自适应调节阈值，以满足不同网络环境下的转发要求.仿真实验表明，此算法与其他算法相比，在较低的传输延迟下大大提高了传输的成功率，降低了网络传输开销.

机会网络；邻居变化率；传输性能；自适应转发

0 引言

机会网络是一种通过节点移动来实现的延迟容忍网络.相对于传统无线网络,机会网络的规模和节点初始位置无法预先设置，以“存储-携带-转发”模式传输信息.由于机会网络可以处理网络分裂、时延等传统网络不能解决的难题，在通信基础设施缺乏、网络环境恶劣等场合得到了广泛的应用[1].然而在机会网络应用过程中，网络被分割成不连通的子区域，数据通信利用节点移动带来的相遇机会来实现，因此怎样选择最优节点进行数据的转发，成为机会网络研究中的难点和热点[2].

为了提高数据传输成功率，文中提出了一种基于节点差异性的机会网络数据转发算法.首先考虑节点的剩余能量和邻居变化率，选择剩余能量大、邻居更新快的节点作为中继节点；然后根据节点对的邻居相似度调节阈值的大小，控制不同节点传输性能和不同网络环境下的转发条件，实现自适应转发决策;最后进行仿真实验，测试算法的性能.

1 相关研究

针对机会网络的数据转发问题，国内外学者进行了大量而深入的研究，提出许多有效的数据转发算法[3].最为原始也最为简单的算法为直接传输(Direct transmission)算法，该算法具有消耗小等优点，但是仅当节点移动到汇聚点的通信范围内，才能进行数据有效传输，且存在延迟大、传输成功率低等不足，限制其应用范围[4].之后有学者提出基于洪泛理论(flooding)的机会网络数据转发算法，较好地降低了延迟，提高了数据传输成功率，但是存在网络资源消耗和丢包现象十分严重的缺点[5].文献[6]提出了一种基于RED策略的数据转发算法，通过消息传输的发生与否计算数据传输概率，并根据节点当前传输概率对参数进行编码，有效提高了数据传输的成功率，但是如何计算参数全凭经验，具有较强的主观性和盲目性.为了减少网络数据转发延迟，降低网络的开销，有学者提出了SW(spray and wait)算法，其数据传输效率与消息副本数量密切相关，当副本规模较大时，延迟小，传输成功率高，但是网络开销比较大[7].针对SW算法存在的不足，许多学者对其进行改进，提出一些改进的SW算法，如SF(spray and focus)算法.相对于SW算法，SF算法提高了机会网络数据转发的性能，但是该转发方式缺乏灵活性，不能自适应不同机会网络的传输要求[8].文献[9]提出了基于邻居节点数目的效用值阈值自适应调整算法，但仅考虑相遇节点数目变化，难以准确描述机会网络传输的实际变化状况.文献[10]提出了一种基于节点性能的机会网络自适应转发算法.

2 网络模型与通信模型

2.1 网络模型

设多个节点随机分布在一个N×N的正方形区域内，该传感器网络的性质为：

1)全部机会网络节点采用Random waypoint运动规律，该运动规律的思想为：在N×N的正方形区域内，节点随机选择起始点S和目的点D，节点的运动速度属于区间[Vmin,Vmax],节点匀速地从点S向点D作直线运行，在D处选取暂停时间，暂停时间属于区间[Tmin,Tmax],并且在该位置节点处于静止状态,从而完成一次运动过程.然后将点D作为下次运动的起始点S，进入下一轮运动，不断重复.

2)以基站作为参考标准，对全部汇聚点进行部署，一旦部署后，汇聚点就不能再移动[11].

3)全部节点均不需要人工维护.

4)各节点当前位置及运动速率通过全球定位系统(Global positioning system， GPS)确定.

5)全部节点的运行时钟保持同步.

网络模型如图1所示.

图1 节点的运行方式Fig 1The operation mode of node

2.2 通信模型

根据传输距离，使用自由空间和多径衰落这两种信道模型.如果通信距离小于某个阈值，使用自由空间信道模型；否则，使用多径衰落信道模型[12].发送长度为kbit、距离为d的消息消耗的能量为[7]

(1)

接收长度为nbit的消息消耗的能量为[7]

(2)

其中eRx为接收1bit消息消耗的能量.

3 转发算法

3.1 节点的剩余能量

一个节点的剩余能量越多，它将消息转发到目标节点的成功率就越高.由于能量百分比难以对节点当前的能量状态进行准确描述，因此对节点的剩余能量Ei进行归一化处理[8]:

(3)

其中，uE为节点i的剩余能量率；Ej是相遇节点j的剩余能量.

3.2 邻居变化率

一个节点的邻居变化率越高，该节点在一定时间内与其他节点相遇的概率就越大.设Ni为节点i的邻居变化率，则[12]

(4)

其中，t和told为当前时刻和上一次更新邻居节点列表的时刻；Ni(t)和Ni(told)分别表示节点i的当前邻居节点列表和上一次的邻居节点列表.同样，对Ni进行归一化处理[8]:

(5)

其中，uN为节点i的邻居变化率比率；Nj是相遇节点j的邻居变化率.

3.3 数据传输性能

节点传输能力的优劣主要通过剩余能量和邻居变化率来估计.一个节点的剩余能量和邻居变化率越高，该节点的数据传输能力就越强.节点i的传输性能为[10]

(6)

其中ω表示权重值，其值大小在0～1.

3.4 转发控制因子

在机会网络数据转发过程，节点性能越优异，它可以承担的传输任务就越多.根据该思想，当两个节点i与j相遇时，可以得到Pi和Pj，如果Pj>Pi，那么节点j的传输性能更优，但这时不一定表示节点i应该转发消息包给节点j.文中数据转发算法参考过邻居相似程度对阈值进行自适应调整，提高数据转发的成功率.设Di,j为节点i相对于节点j的阈值控制因子，则有[9]

(7)

在消息转发中，节点i(携带消息包)与节点j相遇，若满足(8)式的条件，则节点i将该消息转发给节点j;否则，继续等待相遇节点.

(8)

其中Pth为阈值.

综合上述可知，基于节点差异的机会网络数据转发算法的工作流程如图2.

4 仿真实验

4.1 仿真环境及参数设置

为了测试文中提出的转发算法的有效性和优越性，在Windows XP操作系统，Intel(R) Core(TM) i3-2120 2.8 GHz CPU，4 GB RAM环境下，采用Matlab 2012编程，进行仿真实验.同时为了文中算法结果具有可比性，选择SW,Binary spray and wait(BSW)和Epidemic算法进行对比，并选择传输成功率、平均延迟、开销率作为算法的评价标准.仿真参数设置见表1.

图2 转发算法工作流程Fig 2The working process of the forward algorithm

表1 仿真参数设置

图3 不同算法的传输成功率对比Fig 3 The comparison of transmission rate of the different algorithms

4.2 结果与分析

4.2.1 传输成功率比较 在不同节点密度条件下，不同算法的机会网络数据传输成功率如图3所示.从图3可以看出:

1)在相同节点密度条件下，SW和BSW算法的数据传输成功率高于Epidemic算法，这主要由于SW和BSW算法基数据传输效率与消息副本数量密切相关，当副本规模较大时，其延迟小，传输成功率高.

2)相对于SW，BSW和Epidemic算法，文中算法的传输成功率明显提高.例如，节点数为150时，文中算法成功率为0.55，SW算法为0.4，BSW算法为0.43，而Epidemic算法只为0.25，这主要由于文中算法选择剩余能量大、邻居更新快的节点作为中继节点，并根据邻居相似度动态调节阈值，以满足不同网络环境下的转发条件，从而提高了传输成功率.

4.2.2 网络平均延迟比较 在不同时间条件下，不同算法的平均延迟如图4所示.从图4可以看出:

1)相对于Epidemic算法，SW和BSW算法的网络平均延迟得到大幅度改善，具有更优的机会网络数据转发性能，提高了数据传输效率和速度.

2)相对于SW,BSW算法，文中算法的网络平均延迟基本持平，相差不大，平均延迟没有得到较好改善.但是随着时间增加，所有算法由于泛洪机制造成的网络拥塞，导致消息包不能到达目标节点，从而导致机会网络传输平均延迟比较大.

图4 不同算法的网络传输平均延迟比较Fig 4 The comparison of transmission network average delay of different algorithms

4.2.3 开销率比较 在不同节点条件下，不同算法的网络开销率如图5所示.从图5可以看出:

1)在所有算法中，Epidemic算法开销率最大，是其他算法的近10倍，这主要由于Epidemic算法需要大量的额外开销，导致网络资源浪费十分严重.

2)相对于SW，BSW算法，文中算法在开销率方面优势显著，比SW和BSW算法减少了约20%开销，这主要由于文中算法有目的地选择传输能力强的中继节点，并自适应控制转发条件，减少了盲目转发造成的资源浪费.

图5 不同算法的网络开销率比较Fig 5 The comparison of network overhead rate of different algorithms

5 结束语

为了更加充分利用机会网络的能量，有效延长网络生存时间，提高数据传输成功率，提出了一种基于节点差异性的机会网络数据转发算法.该算法充分考虑节点的剩余能量和邻居变化率，以及自适应调节不同邻居相似度下的转发条件.仿真验证实验结果表明，与其他机会网络数据转发算法相比，文中算法不仅提高了网络数据传输的成功率，减少了网络传输延迟，并且大幅度降低了节点间的转发次数，网络传输开销急剧减少.

[1] PELUSI L,PASSARELLA A,CONTI M.Opportunistic networking:Data forwarding in disconnected mobile Ad hoc networks[J].CommunicationsMagazine,2006,44(11):134-141.

[2] CHEN L，YU C，SUN T，et al.A hybrid routing approach for opportunistic networks[C]//Proceedingsofthe2006SIGCOMMWorkshoponChallengedNetworks.Pisa:ACM，2006:213-220.

[3] LEGUAY J，FRIEDMAN T，CONAN V.DTN routing in a mobility pattern space[C]//Proceedingsofthe2005ACMSIGCOMMWorkshoponDelayTolerantNetworking.Philadelphia:ACM，2005:276-283.

[4] 杨波,王雷.高性能的机会网络数据转发机制EH-EC[J]. 计算机应用,2010,20(12):3180-3184.

[5] 钱景辉.一种机会网络中节点转发策略的改进[J]. 微电子学与计算机,2013,30(1):5-8.

[6] GUPTA B,GHOSH K,DUTTA D,et al.Broadcasting in complete and incomplete star interconnection networks [J].InternationalJournalofComputerSystemScienceandEngineering,2001,4(2):205-21.

[7] 刘唐,彭舰,王建忠,等.延迟容忍移动传感器网络中基于节点优先级的数据转发策略[J]. 计算机科学,2011,38(3):140-146.

[8] 龚丁海.机会网络中转发机制的研究[J]. 河池学院学报,2011,31(2):49-51.

[9] 孙利民,熊永平,马建.机会移动传感器网络中的自适应数据收集机制[J].通信学报,2008,29(11):186-193.

[10] 周航,牛建伟,孙利民,等.机会网络中自适应多跳多拷贝传输算法[J].计算机科学,2008,35(11):167-170.

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

[12] 舒坚,杨世伟,刘琳岚.机会网络中的自适应转发控制算法[J]. 计算机应用研究,2011,28(6):2336-2338.

(责任编辑 惠松骐)

Data transmission algorithm of opportunistic networks based on nodes difference

GAO Cai-xia,QI Chang-ping

(College of Information Technology and Media，Hexi University，Zhangye 734000，Gansu，China)

In order to improve the success rate of network transmission,reduce transport costs,a novel data transmission algorithm of opportunistic networks based on nodes' difference is proposed.Firstly,the node residual energy and neighbor update speed is selected as a relay node;and then the threshold is adaptively adjusted according to neighbor similarity node to meet the forwarding requirements under the different network environment.The simulation results show that this proposed algorithm not only has improved the network data transmission probability and reduced the delay of network transmission,and greatly reduce the transmission number of nodes and sharply reduce the network cost compared with other opportunistic network data forwarding algorithms.

opportunistic network;change rate of neighbors;transmission performance;adaptive transmission

2014-10-08;修改稿收到日期:2015-01-25

国家自然科学基金资助项目(61173124)

高彩霞(1976—)，女，甘肃张掖人，讲师，硕士.主要研究方向为数据挖掘与人工智能. E-mail:bixiyadianna@foxmail.com

TP 393.01

A

1001-988Ⅹ(2015)04-0042-04