徐大庆，王 田

(1.长沙大学信息与计算科学系，长沙410003；2.华侨大学计算机科学系，福建厦门 361021)

公共的无线传感器网(WSN，Wireless Sensor Networks)可以由许多冗余的传感器节点组成，每个传感器有一定的计算、存储与通信能力。其主要应用是感知物理环境，把感知的数据传给汇聚点。这些节点通过无线收发器有能力相互通信。作为传感器节点的用户接口，汇聚点是必须的。汇聚点还可通过卫星网、无线或有线Internet服务传送数据给用户。

WSN的地理位置路由协议［1］使用目标节点和前向邻居节点的位置信息决定路由。每个传感器节点的发送范围较小，通过其它中间传感器，前向转发包。在每次的前向跳跃中，传感器节点寻找与目标位置最近的邻居，直到当前的前向转发节点的邻居列表中有目标节点。在最后一跳中，邻居传感器节点直接发送数据包给目标节点。这些邻居节点的路由能够通过周期性的Hello包交流得到维护。只要传感器节点是相对静止，初始化每个传感器与汇聚点的位置信息，地理路由就能被成功运用。然而这样的路由协议存在一个普遍的问题，靠近汇聚点的传感器节点会大大地，很快地减少它们的能量，因为它们需要往前转发从其它许多节点发过来的给汇聚点的信息，长期这样，减少了这些传感器以及整个网络的寿命。并且，如果汇聚点快速移出下个跳跃点的发送边界，从源节点到汇聚点的前向转发就不能正确执行，因为没有移动汇聚点的位置更新，汇聚点不能收到最后的转发。这样产生一些问题，比如，不准确的目标位置产生错误的路由和包丢失。如果使用洪泛协议FLUP(Flooding-based Location Update Protocol)，当汇聚点移动时，其新位置必被传到全部传感器，对于大规模传感器网，这样高负载是没有效率的。汇聚点频繁的位置更新导致传感器节点快速的能源消耗和无线发送冲突增加。文献［2］推出了一个基于局部更新的路由协议LURP(Local Update Based Routing Protocol)，帮助解决这个问题。当汇聚点在一个局部区域内移动时，它只需对局部区域内的传感器，传播它的位置更新信息。

另外与平面路由协议［3－4］等相比，分簇路由协议［5－13］等具有拓扑管理方便、能量利用高效、数据融合简单等优点，成为当前重点研究的路由技术。传感器网络的分簇路由协议的主要缺点是簇划分算法和簇头选举算法比较复杂，因此现有的分簇传感器网络路由协议难以被实际应用。为了解决上述问题，我们提出了一个WSN的基于位置服务器树的位置管理与路由协议LSTLMRP。

1 新协议LSTLMRP描述

假设移动汇聚点没有能量限制，但传感器节点有严格的能量限制。我们只考虑传感器节点的能量消耗。并且，与通信相比，计算的能量消耗很小。所以我们只考虑通信的能量消耗。随着传感器技术的发展，传感器的存储能力，计算能力与通信能力将会提高，能量也将提高，簇内传感器轮流担当簇头将是可行的。利用WSN节点定位机制能够获得各节点的位置信息。

在上述条件下，我们设计了一个新的位置管理与路由协议LSTLMRP。通过建立以汇聚点为根的位置服务器树，接收汇聚点的位置更新，记录汇聚点的当前位置。位置服务器也担任簇头，它收集融合簇内的数据后，沿着位置服务器树将数据多跳传给汇聚点。为了减少与平衡网络通信负载，可以在WSN中设立多个汇聚点，如图1所示。本文定义每个汇聚点负责一个传感器组，一个传感器组是具有某种属性的相关传感器簇的集合。每个汇聚点有唯一的标识码。

图1 传感器及簇头沿SPT传数据到汇聚点

1.1 位置服务器树的建立及汇聚点位置更新

(1)预先把WSN部署区域按实际需要划分成各分区，分区用圆圈表示。传感器按需要配置，分布在各分区内，每一分区为一簇，如图1所示。每个簇内有一个簇头，簇头同时担任位置服务器。每个汇聚点配有一个位置服务器集合，并建造相应的以汇聚点为根的最短路径树SPT(Shortest Path Tree)来覆盖此集合［14］，如图1所示。

(2)为了进一步地减少汇聚点的位置更新的代价，每个汇聚点选择一个以它为中心的目标区域［2］，如图2所示的圆型区域。目标区内的每个位置服务器负责管理一个到这个汇聚点的SPT局部路径，并把收到的包转发给汇聚点。

(3)当汇聚点在目标区域内移动时，汇聚点只向目标区内的位置服务器沿着SPT局部路径发送位置更新。对目标区域外的簇头，不发送位置更新，隐藏汇聚点的短距离移动。

(4)当汇聚点移出目标区域时，它将建立新的目标区域，并且触发新的位置更新，按照本文定义的簇内的传感器节点轮流担任簇头的法则，该汇聚点所管辖的传感器组内的位置服务器(簇头)被全部更新，它的新的位置服务器集合被建立，以汇聚点为根的新位置服务器的SPT也被构造。

(5)汇聚点用以下方式传播位置更新给SPT上的位置服务器。当一个位置服务器LS从汇聚点S(或从SPT的上流位置服务器)收到一个更新消息，它将首先检查S是否为它的最近汇聚点，若是最近的，LS必须局部计算以S为根的SPT，如果这个LS是SPT的叶子节点，它将停止传播过程。否则，LS将局部决定它是否需要沿SPT转发该更新消息给它的下级邻居。如果LS以前从一个上级邻居收到另一个更新消息，并且它知道这个上级邻居有一个比S更近的汇聚点，LS将不沿树转发此更新。当多个汇聚点在同一个簇内时，LS只传播来自其根的更新消息，其他的被扣押。

(6)如果汇聚点长久留在目标区域，为了平衡传感器的负载，我们设计一个超时机制。当汇聚点留在目标区域的时间超过设定的时间时，汇聚点强制启动所有的位置服务器更新。

传感器节点的能量很受限制，通过汇聚点的随机移动，网络中的位置服务器节点随机变化着成为它的位置服务器邻居节点，并且簇内位置服务器的轮流担当避免了在单个节点上过多的能量消耗，均衡了传感器的能量消耗，延长了整个网络的寿命。

1.2 向汇聚点传送数据

(1)簇内路由，如图1所示，每个传感器直接地或通过其它节点转发数据给它的簇头。基本想法是让簇内所有传感器构成一个以簇头为根的树。文献［15］展示了下面几点:①如果在中间点处理数据融合，最小生成树(MST，Minimal Spanning Tree)在簇内消耗最少总能量。②如果簇内中间节点没有数据融合，则SPT消耗最少总能量。

(2)簇间路由，簇头将数据收集融合后沿着位置服务器的以汇聚点为根的SPT多跳传送给汇聚点。这样利用SPT、MST，让传感器传送数据至汇聚点的能耗最小。并且采用多跳传送均衡了传感器的能耗。

2 仿真与性能分析

2.1 仿真环境

在这一节我们比较协议LSTLMRP，LURP和FLUP的移动汇聚点位置更新的平均能耗。FLUP每次传播汇聚点的位置更新到网络的全部传感器，LURP有时对一个局部区域，有时对整个网络，传播汇聚点的位置更新。而LSTLMRP只对汇聚点的局部或整个位置服务器树，传播它的位置更新。这里不要考虑簇头的更新代价。因为簇头的更新并不是为了移动汇聚点的位置更新，而是为了均衡传感器之间的能耗。

我们设置一个传感器组，由一个移动汇聚点管辖，如图2所示。其边长为L，划分成L2个正方格，每个方格为一簇，簇内设有一个位置服务器(簇头)，即有L2个位置服务器。整个区域内有N个传感器节点分布，汇聚点的位置在时间T的周期内改变m次，目标区域的半径为R。汇聚点移出目标区域所耗用的时间周期为t，n是目标区域内传感器的个数。h是发送一次位置更新消息所需的平均能耗。k是目标区域内位置服务器的个数，d是传感器密度。

图2 LSTLMRP仿真环境

2.2 仿真模型

在时间T的周期内，因为汇聚点的位置已经改变了m次，所以LSTLMRP协议的汇聚点位置更新的平均能耗是

局部更新路由协议(LURP)［2］的位置更新平均能耗是

从上面仿真环境假设可以推知:

因为n/(πR2)=N/L2；k/(πR2)=L2/L2，并且t与R成正比；与v成反比；α是常数。另外，m与T、v成正比，β是常数。将式(3)代入式(1)、式(2)得:

FLUP的平均能耗至少是:

2.3 仿真结果及性能分析

本文采用MATLAB仿真工具作仿真，仿真结果的各图的公共参数设置如下:T=120 s；h=0.002 J；d=5 个/m2；α=3；β=0.008。为了体现LSTLMRP 协议与LURP协议的全部性能，我们采用了大规模的无线传感器网作仿真。将式(7)代入式(4)、式(5)、式(6)作仿真可知，LSTLMRP协议的位置更新平均能耗最小，如图3、图4与图5所示。并且位置更新的能耗，随网络边长的增加而增加，如图4所示(其中R=50 m，L=1 m ～1 000 m，v=2 m/s)，也随汇聚点移动速度的增加而增加。如图5所示(其中R=50 m，L=500 m，v=2 m/s～30 m/s)。

LSTLMRP目标区域的大小可以由它的半径R表示，半径R是一个重要参数。一方面，如果半径太小，汇聚点不断地从一个目标区域转到另外一个目标区域，位置服务器及其汇聚点位置信息不得不频繁更新。这样消耗传感器太多的能量，另一方面，如果半径太大，目标区域内的位置服务器将增加，目标区域内的汇聚点的位置更新的能耗将增加。如图3所示(其中R=10 m～500 m，L=500 m，v=2 m/s)，协议LURP 与协议LSTLMRP都有一个低谷，当R取适当值时，它们在时间周期内的位置更新能量消耗为最小。所以在实际应用中，利用此性能分析模型，能得出最小能耗的R值。

图3 以R为变量的位置更新能量消耗比较

图4 以L为变量的位置更新能量消耗比较

图5 以v为变量的位置更新能量消耗比较

并且容易了解R值与网络大小的关系。当网络大小增加时，R值也应该增加。因为网络大小增加时，汇聚点在整个网络的位置更新代价将增加，所以要增加R，减少在网络发送位置更新的次数。

并且，从表达式(1)可以看出新协议LSTLMRP与传感器密度无关，而LURP与FLUP的位置更新能量随传感器密度的增加而增加。所以LSTLMRP很适合于大规模或传感器密度高的场合。

3 结论

协议LSTLMRP通过建立以汇聚点为根的位置服务器的SPT，记录移动汇聚点的当前位置；并为汇聚点建立目标区域，这样大大地减少了移动汇聚点位置更新的平均能耗。传感器将感知的数据沿簇内SPT或MST先传给簇头，簇头将数据收集融合后，沿位置服务器的SPT多跳传送到汇聚点。使得传感器传送数据至汇聚点的能耗达到最小值，簇内的传感器轮流担当簇头及位置服务器，这样能取得传感器之间统一的能源消耗，传感器能量消耗均匀，延长了整个网络的寿命。这个协议也很适合大规模或密度高的无线传感器网。

［1］王殊，阎毓杰，胡富平，等.无线传感器网络的理论及应用［M］.北京:北京航空航天大学出版社，2007.73－93.

［2］Wang Guojun，Wang Tian，Jia Weijia，et al.Local Update-Based Routing Protocol in Wireless Sensor Networks with Mobile Sinks［C］//IEEE ICC 2007 proceedings.2007.3094－3099.

［3］Intanagonwiwat C，Govindan R，Estrin D，et al.Directed Diffusion for Wireless Sensor Networking［J］.IEEE/ACM Trans on Networking，2003，11(1):2－16.

［4］Heinzelman Wr，Kulik J，Balakrishnan H.Adaptive Protocols for Information Dissemination in Wireless Sensor Networks［C］//Proc of the ACM MobiCom’99.Seattle:ACM Press，1999:174－185.

［5］Heinzelman W，Chandrakasan A，Balakrishnan H.Energy-Efficient Communication Protocol for Wireless Microsensor Networks［C］//Proc of the 33rd Annual Hawaii Int’l Conf on System Sciences.Maui:IEEE Computer Society，2000.3005－3014.

［6］Manjeshwar A，Grawal D P.TEEN:A Routing Protocol for Enhanced Efficiency in Wireless Sensor Networks［C］//Proc of the 15th Parallel and Distributed ProcessingSymp.San Francisco:IEEE Computer Society，2001.2009－2015.

［7］Younis O，Fahmy S.HEED:A Hybrid，Energy-Efficient Distributed Clustering Approach for Ad-Hoc Sensor Networks［J］.IEEE Trans on Mobile Computing，2004，3(4):660－669.

［8］牟大年，王长山.WSN中一种能量均衡的路由协议［J］.传感技术学报，2009，22(2):254－257.

［9］卢强，何熊熊，冯远静，等.基于竞争机制的无线传感器网络分簇路由协议［J］.传感技术学报，2010，23(2):245－250.

［10］张文祥，马银花.基于梯度和剩余能量的WSN路由算法研究［J］.传感技术学报，2009，22(8):1182－1185.

［11］毕晓君，张艳双.基于移动代理的无线传感器网络路由算法［J］.传感技术学报，2009，22(7):1007－1012.

［12］王寅，尚凤军，任东海.一种基于蚁群系统的传感器网络QoS路由算法［J］.传感技术学报，2010，23(2):239－244.

［13］沈玉龙，徐启建，裴庆祺，等.基于栅格的无线传感器网络路由方法［J］.通信学报，2009，30(11):96－100.

［14］Yan Yan，Zhang Baoxian，Hussein T Mouftah，et al.Hierarchical Location Service for Large Scale Wireless Sensor Networks with Mobile Sinks［C］//IEEE GLOBECOM 2007 proceedings.2007.1222－1226.

［15］Cristescu R，Beferull-Lozano B.Lossy Network Correlated Data Gathering with High-Resolution Coding［C］//IEEE IPSN Proceedings.2005.218－224.