低开销低延迟WSN多费马点链多地域群播算法*

苏 畅，臧李立，尙凤军，赵 曜

(1.重庆邮电大学计算机科学与技术学院，重庆400065;2.美国康奈尔大学计算机系，纽约州伊萨卡市，美国)

随着无线传感器网络［1］技术的进一步发展，其应用领域越来越广。传感器节点的能量受限以及对数据实时性的高要求使得低能耗和低延迟成为无线传感器网络通信协议的重要衡量指标。基于地理位置的路由协议因其对网络拓扑结构信息的极低需求使其算法简单高效而且开销小，其路由发现和数据传输过程依靠节点自身及其邻节点的位置信息(通过 GPS 等定位设备［2－6］获取)。

无线传感器网络极强的应用相关性使基于地理位置路由的地域群播(Geocasting:即源节点向WSN中特定地理位置区域内的所有节点发送信息)应运而生。其应用广泛，如:森林管理中心需要向森林中高火险区域内所有节点发送命令，使区域内节点及时监测并汇报其周围温度状况;交通控制中指挥中心要向交通拥挤地区所有节点及时发出控制命令。

地域群播通过两个过程完成传输:源节点与目标区域的通信及目标区域内信息的传输。网络拓扑的不规则性，尤其是路由空洞的存在，使信息如何低能耗、高可靠性、低延迟地传输到目标区域成为目前研究的热点。Brad Karp等提出的GPSR算法［7］，以贪心算法为基础，结合面路由的方法，成功解决了贪心算法因遇到路由空洞而导致算法失败的问题;胥楚贵等提出的最佳匹配节点策略［8］通过选取距离由空洞边界所围成多边形的最小覆盖圆圆心最近的非活跃节点来替换失败节点的方式修复覆盖空洞;F.Yu 提出的弹性路由(Elastic Routing)算法［9］通过路由路径的反方向更新Sink节点的位置信息，大大降低了能量开销和传输延迟;针对密集型网络的目标区域内信息的传输多采用简单泛洪的方式，如ALURP［10］、LBM［11］等算法。而实际中网络的密度状况是不可知的，稀疏网络严重降低了网络的连通度［12］，简单泛洪无法保证区域内所有节点收到信息，因此 Karim Seada等提出了 GFPG［13］算法。

多目标区域地域群播的目标区域数量以及位置均未知，这种复杂性注定了单目标区域算法无法满足其需求。多路径单地域群播算法［14］中源节点依次将信息传输到每个目标区域内，能量开销极大;简单目标区域链算法［14］通过链接所有目标区域减少了源节点的能量开销，但整个网络的能量开销依然很大;Lee Sung-Hee等提出的单费马点链算法［12］将所有目标区域与源节点连接到一条费马点链上，如图1(a)所示，虽然可以降低整个网络的能量消耗，但是其健壮性和网络传输延迟存在着缺陷。

图1 多地域群播算法

本文提出一种基于多费马点链低能耗低延迟多地域群播算法，在保持较低能量消耗的基础上，降低了传输延迟，并在NS2环境下对LLA算法和现有的算法进行仿真分析。

1 多费马点链算法

多费马点链算法包括两部分:第1是基于源节点传输区域的网格划分以及网格中簇头的选择，第2是通过引入四边形费马点解决建立三角形费马点失败的问题，如图1(b)所示。

1.1 网格划分及簇头选择

假设数据源节点A的位置坐标为(x0，y0)，则以该节点为中心建立如下坐标系:以直线y=y0为该坐标系的x轴，以直线x=x0为该坐标系的y轴。此坐标系将网络分成四网格。当多数目标区域集中于某一网格中时，按如下规则划分:假设网络中目标区域数量为n，网格划分的层次为N

直到经过N次划分的网格中的目标区域的数量小于等于n/2N或网格中的目标区域数量均≤4。

网格中选取距离源节点最近的目标区域的中心点作为该网格的簇头，不同源节点对于不同的目标区域产生不同的簇头节点，避免了固定或单一簇头导致其消耗能量过快而死亡。

下面对基于源节点传输区域的网格划分及网格中选取距离源节点最近的目标区域作为簇头的方法进行性能分析。

假设有n个目标区域，费马点之间的平均传输延迟为t，费马点到其相邻节点之间的传输延迟平均为 T，则:

⇒delay(n)=nt+T，(delay(n)为第n个节点接收到数据包时的延迟时间)(avg(delay(n))为n个目标区域接收到数据包时的平均延迟时间)。分成网格后，每个网格有n/4个目标区域，由于数据在网格内同时通信，其平均延迟可以认为等同于单一网格的延迟，考虑上面的假设，则:

通过以上分析在传输延迟方面该方法优于单费马点链算法。源节点将信息传送到簇头节点后，由簇头节点通过费马点链转发到相应的目标区域内。

1.2 网格费马点链

网络中目标区域需要向其感兴趣的节点发送位置信息及数据收集请求，源节点则需要记录向其发送请求的所有目标区域的位置信息以便计算费马点链。

三角形中一定存在费马点，如图2所示，寻找△ABC费马点的过程如下。

图2 三角形费马点

在△APC中，将∠PAC按逆时针方向旋转60°，点P和点C分别落于点P1和C'，的最小值即的最小值，即C'到点B的直线距离

这时点P和P1都在线段C'B上，同理我们可得点P必在线段B'A和线段A'C上，三条线段的交点即是三角形的费马点。因此只需找到A'、B'和C'中的任意两点就可以找到该三角形的费马点，如图2所示。

单费马点链算法存在着明显的缺陷:局部能量开销大、极大的传输延迟、可靠性差。当费马点存在于三角形外部时(即三角形任意一内角大于等于120°)，按照顺序往下继续寻找目标区域，然后以这三个目标区域和簇头组成的四边形为基础，寻找四边形的费马点，找到该费马点后，继续寻找接下来的三角形的费马点，直到所有的目标区域都连接到费马点链上。如图3所示，有两种情况:凸四边形(如图3(a)所示)和凹四边形(如图3(b)所示)。两种情况下∠ABC＞120°，因此选取第四个目标区域D形成四边形，计算出四边形的费马点后再以该费马点、簇头A和下一个目标区域的中心点E形成的三角形继续寻找费马点。

图3 四边形费马点链

定理1 凸四边形费马点的位置为对角线的交点。

证明:假设凸▱ABCD中，对角线AC、BD交于点P，如图4所示。

图4 四边形费马点

定理2 内含三角形中内三角形的两边之和小于外三角形的两边之和。

定理3 凹四边形的费马点在凹点上，即四边形内角大于180°的顶点上。

证明:如图5(b)和5(c)两种情况所示:F点均为四边形内部异于凹点的任意一点，在图5(b)中，△CDB是△CFB的内含三角形，由定理2可知:

在图5(c)中，△ADB是△AFB的内含三角形，

由上证明可得出结论:凹四边形的费马点在其凹点上。

图5 四边形费马点

通过引入四边形费马点保证了所建费马点链的连续性，然后源节点将信息沿着费马点链传送到所有的目标区域，到达目标区域的信息在该区域内泛洪，完成地域群播路由过程。该方法能够减少单个网格内节点的能量消耗，降低整个网络的能量开销。

2 仿真结果与分析

2.1 仿真环境

我们使用的仿真工具是NS2.30，MAC层采用的是802.11协议。我们构建了如下的无线传感器网络:400个无线传感器节点随机地分布在2 000 m×2 000 m的正方形区域内，地域群播区域为半径250 m的圆形区域。整个仿真过程中，对每种算法我们分别设定并随机选取网络中的地域群播区域的数量为2、4、6、8、10、12、14、16 个。

仿真中我们采用三个指标来衡量该算法的性能:包的成功传输比率、端到端的平均延迟和数据传输到目标区域内这一过程中的平均能量消耗(下文简称为平均传输能量消耗)。包的成功传输比率定义为网络中所有的目标节点成功接受到数据包的总量与网络中所有数据源节点发送的数据包的总量的比值;端到端的平均延迟定义为网络中所有数据包的延迟的总和与网络中所有数据包总量的比值;平均传输能量消耗定义为网络中所有传输的数据包的总字节数与网络中产生的数据包的总量和数据包成功传输比率的乘积的比值。

2.2 仿真结果和分析

图6展示了数据包的成功传输比率。从图中可以看出单费马点链算法、多路径单地域群播算法和本文中提出的多费马点链算法的数据包的成功传输比率在95.5% ～97%之间波动，多路径单地域群播算法采用的是每次只向一个区域发送数据，而基于费马点链的两种算法的第1阶段都是采用GPSR算法，可以很好的解决导致成功传输比率下降的主要因素——路由空洞，并且对链路进行了优化。当目标区域数量大于6个的时候，简单目标区域链算法的成功传输比率呈现线性下降趋势，当区域数量为12时，成功传输比率已降到95%，数量为16时降到93.5%，因为简单目标区域链算法存在两个方面的缺陷:无法解决路由空洞并且路由路径最长。通过以上分析，多费马点链算法可以有效地保证将数据传输到目标区域，其数据成功传输比率高且稳定。

图6 数据包成功传输比率

图7 端到端的平均延迟

图7展示了端到端的平均延迟。简单区域链算法的延迟明显高于其它3种算法，当区域数量为16时，平均延迟为150 ms，是其它3种算法的300% ～500%;而单费马点链算法的平均延迟高于多费马点链算法，目标区域从4变化到16时，其延迟是多费马点链算法的200%，因为该算法单一的传输链路导致其传输路径过长;目标区域大于10的时候，多路径单地域群播算法的延迟比多费马点链算法高出30% ～40%，因为其延迟主要由两部分组成:数据传到第1个和最后1个目标区域的时间和事件在队列中的等候时间，而多费马点链算法是在4个网格同时通信，因此目标区域数量对其的影响仅为其它算法的1/4。通过以上分析，多费马点链算法在平均延迟上要明显好于其它3种算法。

图8展示了网络中的平均传输开销。当区域数量为4的时候，4种算法的平均开销基本相同，为7 kbit;区域数量大于6时，简单区域链算法和多路径单地域群播算法的开销，明显高于基于费马点链的算法，目标区域数量从10开始一直到16，其开销比其它基于费马点链的算法平均高出20%～30%。因为基于费马点链的两种算法对传输链路进行了优化，链路数要比以上两种算法少。通过以上分析，单费马点链算法和多费马点链算法在平均传输开销上明显低于简单区域链算法和多路径单地域群播算法。

图8 平均传输开销

3 结束语

多地域群播的目标区域数量和位置均未知，这种复杂性导致目前无线传感器网络多地域群播算法都无法做到能量和传输延迟的平衡。本文提出了一种新的基于多目标区域的多费马点链算法，主要思想是以源节点为中心将自身传输区域分为4个网格，网格中选取距离源节点最近的目标区域的中心点为簇头，并以该簇头与目标区域形成三角形与四边形相结合的费马点链。通过仿真实验表明多费马点链算法在保持较低能量消耗的同时大大降低了传输延迟。

［1］ Akyildiz I F，Su W L，Sankarasubramaniam Y.A Survey on Sensor Networks［J］.Communications Magazine，2002，40(8):102－114.

［2］ Li J Y，JAnnotti J，Couto D，et al.A Scalable Location Service for Geographic Ad Hoc Routing［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，New York，2000:120－130.

［3］ Xue Y，LI B C，Nahrstedt K.A Scalable Location Management Scheme in Mobile Ad-Hoc Networks［C］//Proc.LCN 2001.26th Annual IEEE Conference，Tampa，2001:102－111.

［4］ He T，Huang C，Blum B，et al.Rangefree Localization Schemes for Large Scale Sensor Networks［C］//Proc.of the 9th Annual International Conference on Mobile Computing and Networking，2003:81－95.

［5］ Seada K，Helmy A.Rendezvous Regions:A Scalable Architecture for Service Location and Data-Centric Storage in Large-Scale Wireless Networks［C］//Parallel and Distributed Processing Symposium，Proc.18th International，2004:218－225.

［6］ Stojmenovic I，Liu D D，Jia X H.A Scalable Quorum-Based Location Service in Ad Hoc and Sensor Networks［C］//Mobile Adhoc and Sensor Systems，Vancouver，2006:489－492.

［7］ Karp B，Kung H T.GPSR:Greedy Perimeter Stateless Routing for wireless Networks［C］//Proc.of the 6th Annual International Conference on Mobile Computing and Networking，Boston，2000:243－254.

［8］ 胥楚贵，邓晓衡，邹豪杰.无线传感器网络覆盖空洞修复策略［J］.传感技术学报，2010，23(2):256－259.

［9］ Yu F，Park S，Lee E，et al.Elastic Routing:A Novel Geographic Routing for Mobile Sinks in Wireless Sensor Networks［C］//IET The Institution of Engineering and Technology，2010，4(6):716－727.

［10］ Wang G，Wang T，Jia W，et al:Adaptive Location Updates for Mobile Sinks in Wireless Sensor Networks［J］.The Journal of supercomputing，2009，47(2):127－145.

［11］ Ko Y B，Vaidya N H.Flooding-Based Geocasting Protocols for Mobile Ad Hoc Networks［J］.Mobile Networks and Applications，2002，7(6):471－480.

［12］ Seada K，Helmy A.Efficient Geocasting with Perfect Delivery in Wireless Networks［C］//Proceedings of IEEE WCNC 2004，Atlanta，2004，4:2551－2556.

［13］张强，孙雨耕，刘丽萍.边界节点对无线传感器网络连通性的影响［J］.传感技术学报，2011，24(5):737－741.

［14］ Lee S H，Ko Y B.Efficient Geocasting with Multi-Target Regions in Mobile Multi-Hop Wireless Networks［C］//Wireless Networks.2010，16(5):1253－1262.