基于两步前向区域空洞预测的WMSNs路由算法

2015-05-05刘浩程黄可心

传感技术学报 2015年1期

关键词：空洞路由投影

孙毅,刘浩程,陆俊,黄可心

(华北电力大学电气与电子工程学院,北京 102206)

基于两步前向区域空洞预测的WMSNs路由算法

孙毅,刘浩程*,陆俊,黄可心

(华北电力大学电气与电子工程学院,北京 102206)

针对WMSN中的空洞问题,使用两步前向区域进行空洞的预测,并使用投影距离代替贪婪算法进行选路,提出了TFAP(Two steps Forward Area Prediction)算法。仿真结果表明,TFAP算法改善了QoS延迟和网络性能(两步前向区域空洞预测有效进行空洞优化,投影距离也能优化网络性能)。

无线多媒体传感器网络;路由算法;空洞预测;前向区域

无线多媒体传感器网络WMSNs(Wireless Multimedia Sensor Networks)[1],是由一种多媒体传感器节点形成的自组织分布式无线网络,WMSNs作为传感器网络的高级形式,已成为一个崭新的研究领域,同样也伴随着新的挑战。QoS的需求是WMSNs区别于传统WSNs的一个重要标志,传统WSNs通常以牺牲QoS以换取节点的能量使用最大化为目的,而WMSNs更多考虑的是实时性,可靠性,带宽等服务质量[2-3]。

WMSNs的路由协议以保障QoS为首要目标,同时考虑能量最优策略。其中,SAR(Sequential Assignment Routing)协议[4]是第1个考虑QoS保障的WSNs路由协议,该算法首先反向建立多条路径,再根据能量等参数选择最优路径,缺点是节点中的大量冗余信息消耗了大量能量和代价,可拓展性差,在大规模的WMSNs中可能无法使用。SPEED协议[5]是一个基于地理位置信息的无状态实时路由协议,该算法根据选择速率大于中继速率的邻居节点来提供软实时的QoS保障,缺点是没有考虑MWSNs的网络和节点的能量特性。

WMSNs的路由协议随着定位算法的不断演进,其中的地理位置路由得到广泛应用。TPGF(Two Phase Geographic Greedy Forwarding)[6]简约高效,通过反向精简大大减少了路径节点数,有效降低了延迟。但是在遇到空洞时采用标记回退策略,具有一定随意性,经常出现长距离空洞绕行问题[7]。本文主要针对空洞问题和贪婪前进提出TFAP算法,算法通过两步前向区域进行空洞的预测,进行空洞避免,通过投影距离保证每一步前进距离最远。减少了路径节点个数,降低了网络时延,也在一定程度上优化了网络性能。

1 系统模型

(1)

其中:

(2)

由式(1)、式(2)可知,在传输范围R超过门限值d0时,能量消耗将会快速增加,某些节点将会极快的消耗掉能量,缩短网络的生命周期。本算法中限定节点的传输范围R

图1 前向区域的定义

2 两步前向区域空洞预测算法

2.1 算法设计

如图1所示是A节点的前向区域示意图。A为传感器节点,Sink节点是最终目的节点。A节点的前向区域定义是:以A节点为圆心,A节点的通信距离R为半径的圆⊙A与以Sink节点为圆心,A节点到Sink节点的距离d(A,Sink)为半径的圆的相交部分的集合。A节点的前向区域FTA(Forward Transmission Area)表示为:

FTA(A)=⊙A∩⊙Sink

(3)

其中⊙A,⊙Sink分别表示以A和以Sink为圆心的圆。

如图2所示,A节点的一步前向区域为图中空白区域,一步前向区域内的点称为一步前向验证点FTN(First Test Nodes):

图2 两步前向区域空洞预测原理图

图3 几何投影距离计算原理图

FTN(A)={N(x)∈FTA(A)}

(4)

图2中点B、C就是一步前向验证点。图中竖向阴影区域和横向阴影区域分别是一步前向验证点B、C的两步前向区域SFTA(Second time Forward Transmission Area)。其中节点B的两步前向区域内具有节点D、E,而节点C的两步前向区域内有没节点,将两步前向区域内具有节点的点称为两步前向验证点STN(Second Test Nodes):

STN(A)={N(x)∈FTA(A)∩SFTA(N)≠∅}

(5)

本文算法在两次前向验证点中选取几何投影距离PD(Projection Distance)最大的点作为下一跳,即:

Next_node=max(PDi=i1,…in)

(6)

其中i1,i2,…,in表示A节点的所有两步前向验证点。

如图3所示,是几何投影距离计算原理图。

其中A点坐标为(xi,yi),B点坐标为(xj,yj),Sink点坐标为(0,0)。

其中:

(7)

(8)

(9)

将式(5)～式(7)代入可推导得出B节点的投影距离坐标表示为:

(10)

使用投影距离来选择下一跳,保证了每一次选路时,选择的这一跳都朝Sink节点前进了最大的距离,能最快到达Sink节点。

2.2 算法实现

本文算法基于地理位置信息,具有良好的扩展性,适合于大规模网络。本文算法可以对空洞进行预测并对路径进行优化,尽可能减少跳数,并采用投影距离保证每一跳朝Sink节点的前进距离都是最大的。具体算法描述如下:

①判断Sink节点是否在一跳可达的范围内,如果Sink节点一跳可达,则建路成功,直接跳到步骤⑥,否则到下一步。

②计算该节点的一步前向区域FTA(A),通过式(4)确定一步前向验证点FTN(A)。

③计算一步前向验证点的两步前向区域SFTA(N),通过式(5)确定两步前向验证点STN(A)。

④对每个两步前向验证点STN(A)通过式(10)计算其投影距离。

⑤在两步前向验证点STN(A)中选取投影距离最大的点作为下一跳。执行步骤①。

⑥按照TPGF的精简原则,从源节点到Sink节点进行精简,剔除路径中可能出现的环路,并将剔除的节点进行初始化,标记为可用节点。

图4 TPGF选路结果

如图4和图5所示,分别为节点个数n=150时,TPGF和本文算法遇到一个空洞时建立的路径图。如图4,TPGF在A点进行选路时,根据贪婪算法选择了B点作为下一跳节点,B节点的邻居节点内没有比B节点离Sink节点更近的节点,也就是在B节点遇到了空洞。根据TPGF选路原则,将在B节点进行边缘转发,选取了D节点作为下一跳节点。如图5,本文算法在A节点进行选路时,判定A节点的一步前向区域内有B、C两个节点,B、C节点是一步验证点。分别对B、C节点的两步前向区域内是否有节点进行判定,B节点的两步前向区域内不具有节点,也就是在B节点会遇到空洞。而C节点的两步前向区域内具有节点,也就是在C节点不会遇到空洞。根据本文算法,在A节点选路时,已知道选B节点作为下一跳时会遇到空洞,因此把C节点作为A节点的下一跳。从图中可以知道,本文算法有效地避开了空洞区域,减少了节点个数。

图5 本文算法选路结果

3 仿真结果及分析

3.1 仿真环境设置

本文使用了MATLAB7.1对TPGF及本文算法分别进行了仿真。仿真设置在600m×400m的范围内,目的节点位置在(0,0)处,源节点为拓扑右上方距离目的节点的最远节点,能量参数采用文献[5]、[10]的能量模型进行能量统计,仿真环境参数如表1。

表1 仿真实验中的参数设置

3.2 QoS性能实验

本文采用同文献[5,10]中相同的时延统计原理进行统计,时延:

De2e=k*(Dhop+Dotherfactors)

(11)

其中k表示路径节点个数,Dhop表示节点间传输时的延时,Dotherfactors表示MAC层和队列的时延,Dhop+Dotherfactors为一定值,取20ms。可知,该条路径的延迟与路径节点个数成正比,也就是说路径节点个数的统计也就显示了路径延迟的对比。

如图6所示,在区域内节点个数n=150、155、160、165、170、175、180、185、190、195、200时,遇到一个空洞,本文算法与TPGF路径节点个数对比,也是建立的路径的延迟对比。

图6 不同节点密度路径上节点个数对比

不同节点个数延迟优化百分比如表2所示,由表可知平均时延减低了9.2%。在遇到一个空洞时,本文算法相较于TPGF可以有效减少平均传输时延,更加满足无线多媒体传感网对于QoS的需求。

表2 相比TPGF延迟优化百分率表

3.3 网络性能实验

本文以第1个节点死亡时终止发送数据包,统计了网络的初始能量和剩余能量以及能量消耗。在节点个数n=150时,没有遇到空洞时的能量消耗如图7所示。横坐标表示从源节点到Sink节点发送数据包的轮数,纵坐标表示路径上节点的剩余总能量。

图7 n=150时没有空洞的能量消耗图

两种算法都在160轮左右出现第1个死亡节点,原因是在建路时,两种算法在建路时都使用了同一个节点,而该节点能量消耗最快,成为了第1个死亡节点。在本文算法中,第1个节点出现死亡时网络余能量为4.32J,而TPGF第1个节点出现死亡时网络剩余能量为5.21J。计算可得本文算法能量利用率为77.3%,而TPGF能量利用率为72.6%。可知在没有遇到空洞的情况下,本文使用前向投影距离来选择下一跳也能够在一定程度上提高能量利用率。

如图8所示,横坐标表示从源节点到Sink节点发送数据包的轮数,纵坐标表示路径上节点的总能量。TPGF在第150轮时出现第1个死亡节点,而本文算法在第160才出现第1个死亡节点。原因是TPGF的路径中的第1个死亡节点处于空洞边缘,相距邻居节点距离较远,能量消耗最快。在本文算法中该节点在建路过程中没有被选择,也在某些情况下提高了网络的生命周期。

图8 n=150时有一个空洞时能量消耗图

图9 随机运行20次的空洞解决效率图

为了分析本文算法的有效性,选择了150～200个节点分别进行了20次随机运行,分别改进了6、3、5、3、4,1次空洞。随着节点个数的增加,由于空洞几率变小,进行空洞预测并避免的次数也相应成减少趋势。本文算法完全解决了一共出现的22个空洞,解决效率100%。

TPGF算法需要掌握邻节点的位置信息,邻节点之间需要发送信息告知对方自己的位置,这一过程消息复杂度大约为O(n),在进行反向精简时,需要再次进行邻节点信息交互,这一过程消息复杂度大约为O(n),TPGF的算法复杂度大约为O(2n)。进行两步空洞预测需要进行多一次的地理信息交互过程,把自己的邻居节点位置告诉自己的邻居,该过程消息的复杂度为O(2n)。反向精简过程消息复杂度大约为O(n),因此,本文算法复杂度大约为O(3n)。本文算法对比TPGF算法复杂度大概增加了50%,但是结合本文算法的有效性和对能量的优化情况,本文算法还是有一定的可取之处的。

4 结论

本文针对WMSNs中的路由空洞问题,采取两步前向区域进行空洞预测,尽最大可能避免了在空洞区域的绕行,并且采用投影距离代替贪婪算法保证了每一跳前进距离的最大。通过MATLAB仿真表明,本文算法能有效避免遇到空洞,减少了路径节点个数,降低了时延,在增加了一定开销的情况下,在能量利用率和网络生命周期上有一定改善。

[1]李芳敏,李姮,刘新华.无线多媒体传感器网络体系结构及QoS保障机制[J].计算机科学,2009,36(6):19-25.

[2]周灵,王建新.无线多媒体传感器网络路由协议研究[J].电子学报,2011,39(1):149-156.

[3]李芳敏,方艺霖,李姮,等.无线多媒体传感器网络QoS区分服务路由机制[J].电子学报,2010,38(10):2322-2327.

[4]Sohrabi K,Gao J,Ailawadhi V,et al.Protocols for Self-Organization of a Wireless Sensor Network[J].IEEE Personal Communications,2000,7(5):16-27.

[5]He T,Stankovic J A,Chenyang Lu,et al.SPEED:A Stateless Protoco l for Real Time Communication in Sensor Networks[C]//Proceeding of International Conference on Distributed Computing Systems.Washington:IEEE Computer Society,2003:204-223.

[6]Lei S,Yan Zhang,Yang L T,et al.Geographic Routing in Wireless Multimedia Senor Networks[C]//Proceedings of the Second International Conference on Future Generation Communication and Networking.New York:IEEE Communication Society,2008:68-73.

[7]田乐,谢东亮,任彪,等.无线传感器网络贪婪转发策略中的路由空洞问题[J].电子与信息学报,2007,29(12):2996-3000.

[8]Heinzelman W B,Chandrakasan A P,Balakrishnan H.An Application Specific Protocol Architecture for Wireless Microsensor Networks[J].IEEE Trans on Wireless Communications,2002,1(4):660-670.

[9]刘铁流,巫咏群.基于能量优化的无线传感器网络分簇路由算法研究[J].传感技术学报,2011,24(5):107-114.

[10]Zhang L,Manfred Hanswirht,Lei Shu,et al.Multi Priority Multi Path Selection for Video Streaming in Wireless Multimedia Sensor Networks[J].Lecture Notes in Computer Science on Ubiquitous Intelligence and Computing,2008,5061:439-452.

[11]Zhang Degan,Li Guang,Zheng Ke et al.An Energy-Balanced Routing Method Based on Forward-Aware Factor for Wireless Sensor Networks[J].IEEE Trans on Industrial Informatics,2014,10(1)765-773.

[12]尚凤军,任东海.无线传感器网络中分布式多跳路由算法算法研究[J].传感技术学报,2012,25(4)67-74.

A Routing Algorithm Based on Two Steps Forward Area Prediction for Holes in Multimedia Wireless Senor Networks

SUNYi,LIUHaocheng*,LUJun,HUANGKexin

(College of Electrical and Electronic Engineering,North China Electric Power University,Beijing 102206,China)

The problem of holes in the WMSNs have appeared in the perimeters,two steps forward area has been used to predict holes,and projector distance has been used instead of greedy algorithm.Two steps Forward Area Prediction(TFAP)has been present.The simulation results show that TFAP algorithm has improved quality of service and network performance.Two steps forward area prediction has optimized holes effectively and projector distance can also optimize network performance.

MWSN;routing algorithm;holes prediction;forward transmission area