基于混沌过滤机制的高速无线移动网络路由算法的研究

田　祎

(商洛学院 经济与管理学院， 陕西 商洛　726000)



基于混沌过滤机制的高速无线移动网络路由算法的研究

田祎

(商洛学院 经济与管理学院， 陕西 商洛726000)

为解决高速无线移动网络路由发现过程中洪泛效应严重、数据干扰性能降低、难以实现数据链路的发现和维护等问题。提出一种新的基于混沌过滤机制的新路由算法,该算法根据网络数据流量及数据结构的影响,根据相邻信息及数据传输跳度因素来确定路由发现过程中数据发送效率,尽量减少数据冗余及损耗。仿真实验表明,提出的新算法可以有效地降低洪泛效应及网络数据传输质量,增加网络稳定运行时间,具有一定的实际部署意义。

网络路由;性能干扰;混沌过滤;跳度效率机制;冗余洪泛

随着各种高速通信终端的飞速发展,通过一定的组网技术组成一种高速无线移动网络以实现数据在各种终端中的传输,成为一种高速发展的技术[1]。针对节点的有限特性以及高速拓扑的不稳定性,人们往往通过一定的路由技术来实现对高速无线移动网络的数据高效处理,实现数据信息的高效稳定传输[2]。

由于高速无线移动网络中的数据高峰和低谷往往能以一定的概率出现,因此可以通过一定的手段将这种概率性压力进行条件转移,以便降低通信冗余及信息丢失。Ahlswede R[3]等提出一种网络流言路由发现机制,通过发送随机流言信息包,按概率实现路由发现。仿真实验表明，该机制可以有效地降低低流量情况下的网络路由能量控制开销，但该算法在网络流量极大时难以实现顺利流程对接,导致高流量情况下的路由能量控制开销反而会增大。Jamal.N.A[4]等验证了在较低波出现概率的情况下,采用一定的路由请求包可以实现整个网络近似100%的覆盖。仿真实验表明，在低拓扑变动因素下网络路由缺失效应得到很大程度的改善。然而,该技术在拓扑结构高速变化时节点难以匀速发送路由请求包,导致RREQ请求难以及时得到回应。Nguyen D[5]针对节点分布不均匀的高速无线移动网络,提出可以采取按概率覆盖的模式。仿真表明，该算法在一定受限资源对不均匀分布节点的可实现全覆盖，但该算法未考虑混沌扰动因素,导致该技术在节点数量迅速增加时,网络冗余性能也会随之提高。

对此,本文针对传统研究过程中的局限因素,综合考虑网络拓扑结构及网络运行状况因素调整信息包转发概率,最终实现对合适路由需求的较高概率调整转发,实现路径传输的最优化,最终降低网络传输开销。最后,测试了本文算法的网络性能。

1　基于混沌过滤机制的高速无线移动网络路由算法

1.1网络信息包转发概率的计算

在高速无线移动互联网的路由发行过程中,一般而言，节点在任意的网络环境下对于路由请求信息包的转发概率是按照相同节奏进行转发的[6]。倘若当前网络状况不佳,出现严重的网络拥塞现象,且某些节点因网络拥塞而难以发挥效能的情况下,按照相同概率进行信息包的转发可能会造成更严重的网络拥塞现象[7]。

由于针对任意一个网络节点而言,其网络拥塞程度可以依照节点拥塞、连续多跳节点状况、信息传输跳数来确定[8]。故本文通过这种网络拥塞程度来确保移动的RREQ信息包能够准确地进行传输。详细步骤如下所示:

Step 1按照负载程度对网络节点进行排序,以小概率传输到负载程度较大的节点;

Step 2按照路径跳数进行第二次排序,按照跳数较少的路由承担更大概率的信息包传输原则进行传输;

Step 3进行完Step 1、Step 2 之后,继续按照一定的周期T进行排序,直到信息包被全部传输,并搜寻到一条最佳路由。

根据上述步骤,信息包转发概率计算过程如下:

1)首先根据当前节点的状况来计算RREQ信息包在某条路由上成功传输的概率prec(q)。

节点的负载程度,可以根据一定周期内到达该节点的RREQ信息包数量及排队状况而决定。在具体的某个时刻t0到达节点的信息包服从泊松分布,且分布指数为λ,整个信息包组的节点服务时间X服从相同的分布且信息包之间及信息包组之间处于互相独立的状态。因此整个信息流的期望程度NQ可由如下的公式决定:

(1)

其中E[X2]为泊松分布的二阶矩[9],E[X]为泊松分布的期望首先进行网络状况比对,如果网络状况较好,RREQ信息包对应的路由成功传输概率prec(q)很高;如果整个网络状况较差,导致节点处于拥塞状态的话,则经过节点进行RREQ信息包传输过程将不顺利,即:

(2)

其中phigh为接近1的常数;plow处于0～1之间,随着网络状况的下降而处于动态下降的状况。

2)根据路径跳数及节点信息来确保RREQ的转发概率。

首先，节点依据路径跳数及剩余的路由传输跳数h′来确定转发概率preq,保证RREQ信息包必定能够以prec(q)来传输到目的节点。

由于preq的鲁棒性很强，因此在经过若干h′依然可以保持一定程度的可接受误差,即

(preq)h′=preq(q)。

(3)

其中h′为当前跳数h的函数,该函数由如下的表达式所决定:

(4)

其中，β为整个路由发现过程中的最大跳数,h可以由RREQ信息包中的数据报文解析得到。

设当前节点为Nc，其上一跳节点为Np,下一跳节点为Nnest,整个网络中处于Np及Nnest交叉覆盖的节点个数为m。则当前节点Nc对信息包的转发概率pturn由下式决定:

(1-pturn)m=1-preq。

(5)

在高速无线移动中设通信节点的通信半径为r,则整个交叉覆盖区域的面积大小由下式决定:

(6)

经简化,式(6)可写为

s=4πr2。

(7)

结合式(5)可得当前节点Nc对信息包的转发概率pturn为

(8)

(9)

据式(8)，(9)可知当前节点在整个周期T内的整个成功转发概率p为

(10)

prec(q)满足:

(11)

1.2算法流程

根据当前节点Nc对信息包的转发概率pturn的计算来实现对信息包的处理,具体处理信息包的流程如下所示:

Step 1首先进行路由发现,若没有成功进行路由发现时才进行RREQ信息包的分发。

Step 2中间节点进行RREQ信息包的确认工作,一旦收到信息包,转Step 3;反之,继续进行Step 1。

Step 3当仅当该节点是第一次确认信息包时,且当前路由表中存在一条可用链路,则进行信息反馈信息包RREP的发送,否,则转Step 4。

Step 4Step 失败之后,确认该节点的ID并计算该节点的pturn和prec(q)。一旦当前节点没有进行转发则进行信息包分组,当仅当周围节点的剩余跳数较小时候才进行信息分组转发,并转Step 5。

Step 5当前节点在下个时刻收到过相同RREQ信息包,则直接丢弃,转Step 6,反之,继续转向Step 4。

Step 6当仅当收到相异RREQ信息包,则向前一节点发送RREQ信息包进行反馈,并转Step 7。

Step 7当经过一个周期之后,如果当前节点依然没有发现一条可用路由,则可能出现随机路由断开的问题。此时继续进行Step 1 开始,直到能够发现一条可用路由为止。

详细流程图如图1所示。

图1　算法流程图Fig.1　Algorithm flow chart

2　仿真实验

2.1仿真环境设置

为评估本文提出的算法性能,仿真实验中使用NS-2仿真平台对DSR[10]，AG_DSR[11]算法与本文算法进行仿真对比。实验仿真参数如表1所示。

表1　仿真参数表

仿真实验中,为验证本文方案的有效性,实验重点从移动节点个数、网络内节点个数以及节点初始能量大小这3个变量,与DSR，AG_DSR算法在网络数据分组投递率、网络平均正常运行时间及平均能量消耗这3个指标上进行对比。

2.2仿真结果与分析

2.2.1移动节点个数对分组投递效率的影响从图2中可以看到,随着网络中节点个数的不断增加,采用DSR及AG_DSR算法的分组投递效率呈现下降趋势,特别是AG_DSR呈现加速下降的趋势。而本文算法所对应的分组投递效率的下降程度与DSR及AG_DSR相比要低。这是因为随着网络中节点个数不断增加,网络节点的拥塞程度也不断增加[12-13],而本文提出的算法能够依据网络中节点拥塞情况动态的维护路由,特别是在拥塞程度较大时可以有效地维护路由不至于没有收到RREQ信息包而发生断裂,因此减少了拥塞程度较高时网络信息丢失的现象,从而提高了分组投递率。

图2　网络节点密度对网络分组投递率的影响Fig.2　Effect of network node density on the network packet deliverg rate

2.2.2移动节点个数对网络稳定运行时间的影响从图3、图4中可以看到,随着网络中移动节点个数的不断增加,采用DSR及AG_DSR算法的网络稳定运行时间呈现下降趋势。这是由于在网络中移动节点不断增加的情况下,网络拓扑结构的变化也十分频繁,这直接导致网络中各个移动节点在传输数据包时的丢包率也随之上升,导致网络难以正常的运行。而本文算法通过控制转发概率,特别是可以动态依据概率来选择最佳的下一跳节点进行数据传输,因此大大降低了网络丢包现象,从而提高了网络正常运行时间。

图3　高节点密度对网络平均正常运行时间的影响Fig.3　Effect of high node density on the arerage network uptime

图4　低节点密度对网络平均正常运行时间的影响Fig.4　Effect of low node density on the arerage network uptime

2.2.3节点初始能量对网络平均正常运行时间的影响从图5中可以看到,随着节点初始能量的不断增加。采用DSR及AG_DSR算法时网络平均正常运行时间并未得到较好的改善。这是由于随着节点初始能量的不断增加,移动节点数据传输效能在节点移动频繁时候呈现不断下降的趋势,导致网络的正常运行受到不必要的干扰。本文算法充分考虑了拓扑结构剧烈变动时导致的数据报文难以解析的现状,在拥塞严重时大大增强数据链路维护报文的准确性能,因此改善了链路质量,从而大大增强了网络正常运行的稳定性。

图5　节点初始能量对网络平均正常运行时间的影响Fig.5　Effect of node initial energy on the arerage network uptime

图6　周期T取值对网络分组投递率的影响Fig.6　Effect of period T value on the network packet delivery rate

2.2.4周期T取值对网络分组投递率的影响从图6可以看到,随着周期T的不断增加,本文算法与对照组算法均呈现网络分组投递上升的情况,这是由于随着周期T的不断增加,可用于投递数据的时间也随之增加,因而提高了网络分组投递率。然而本文算法的网络分组投递率始终高于对照组算法,这是由于本文算法能够依照网络节点拥塞情况维护路由,降低了拥塞发生的概率。而对照组算法均采用简单投递方式,因而一旦发生拥塞,即导致网络分组投递率出现下降的现象。

3　结　语

由于高速无线移动网络往往采取洪泛类的路由发现机制,导致采取了优化条件之下依然容易造成严重的数据拥塞现象,导致网络性能出现较大程度的下降[14-15]。本文提出一种新的基于混沌过滤机制的新路由算法,该算法根据网络数据流量及数据结构的影响,根据相邻信息及数据传输跳度因素来确定路由发现过程中数据发送效率,尽量减少数据冗余及损耗。仿真实验也表明与传统的DSR及AG_DSR算法相比,本文提出的算法有较强的优越性,具有一定的实际部署价值。

[1]罗守山,杨文川,萧蔷.基于矢量安全传输评估的模型及研究[J]. 北京邮电大学学报,2013,31(3):5-9.

[2]EKMAN F, KERANEN A, KARVO J, et al. Working day movement model[C]//Proceedings of the 1st ACM SIGMOBILE workshop on Mobility models. ACM, 2008: 33-40.

[3]AHLSWEDE R, CAI N, LI S Y R, et al. Network information flow[J]. IEEE Trans. on Information Theory, 2014, 46(4): 1204-1216.

[4]JAMAL N A, AHNED E K. Routing techniques in wireless sensor networks:a survey[J].IEEE Wireless Communication, 2014, 11(6):87-89.

[5]NGUYEN D, TRAN T, NGUYEN T. Wireless broadcast using network coding [J]. IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925.

[6]LUO H,YE F,CHENG J. Two-tier Data Dissemination in Large-scale Wireless Sensor Networks[J].Wireless Networks, 2011, 11(2):161-175.

[7]HEINZELLNAN W B,CHANDRAKASAN A P,Balakrishnan. An Application Specific Protocol Architecture for Wireless Nerworks[J].IEEE Transactions on Wireless Communications, 2012(4):660-670.

[8]CJEM A,KUMAR S,LAI T H. Local barrier coverage in wireless sensor nerworks[J].IEEE Transactions on Mobile Computing, 2012,10(4):491-504.

[9]AMMARI H M,DAS S K.A study of K-coverage and measures of connectivity in wireless sensor networks[J].IEEE Transactions on Computers,2011,59(2):258-267.

[10] WANG L, GENG X. A Community-driven Hierarchical Message Transmission Scheme in Opportunistic Networks[J]. Smart Computing Review, 2011(1): 85-94.

[11] JOLLIFFE D, TRAN T, NGUYEN T. Data mining network coding [J].IEEE Trans. on Vehicular Technology, 2009, 58(2): 914-925.

[12] LEE W.A data mining framework for constructing features and models for instrusion detection systems[D].New York:New York Computer Science Department of Columbia University,2012: 33-76.

[13] 杨林, 郑刚. 无线多跳网中具有网络编码意识的机会路由协议 [J].清华大学学报(自然科学版), 2010, 50(10): 1713-1717.

[14] CHI K K, JIANG X H, YE B L. Efficient network coding-based loss recovery for reliable multicast in wireless networks [J].IEICE Trans. on Communication, 2010, 93 (4): 971-981.

[15] YANG Z, ZHANG Q, WANG R. On storage dynamics of space delay/disruption tolerant network node [J].Wireless Networks, 2014, 20(8): 2529-2541.

(编辑亢小玉)

A chaotic filtering mechanism based high speed wireless mobile network routing algorithm

TIAN Yi

(Faculty of Economics and Management, Shangluo University, Shangluo 726000， China)

In order to solve the problem of flooding effect in the process of high speed wireless mobile network route discovery, the data interference performance is reduced, and it is difficult to realize the discovery and maintenance of data link. In this paper, a new routing algorithm based on chaotic filtering mechanism is proposed, which is based on the influence of network data traffic and data structure. The data transmission efficiency is determined by the factor of adjacent information and data transmission. The simulation results show that the new algorithm can effectively reduce the flooding effect and the quality of network data transmission, and has a certain practical significance.

network routing; performance jamming; chaotic filtering; jumping efficiency mechanism; redundant flooding

2015-11-05

陕西省自然科学基金资助项目(2015JM6347)；商洛学院服务地方专项基金资助项目(15SKY-FWDF003)；商洛学院教改基金资助项目(15JYJX135)

田祎，男，陕西商南人，从事计算机应用技术研究。

TP393

A

10.16152/j.cnki.xdxbzr.2016-04-011