基于网格拓扑的无线传感器网络低能耗路由策略

张江丰

（浙江大学电气工程学院，浙江杭州 310027）

0 引言

无线传感器网络是由一组微型传感器节点以自组织方式构成的无线网络，其目的是协作地感知、采集和处理网络覆盖的地理区域中感知对象的信息，并发布给观察者［1，2］。如今，集成了传感器技术、无线通信技术、嵌入式系统和微处理技术的无线传感器网络已经取得了快速的进展，并被广泛应用于各个领域［1］。如何有效减少无线传感器网络的能量消耗、延长网络的生存时间一直是研究的热点与难点。无线传感器网络的能量主要消耗在节点间的通信上［3］，选择合适的数据包传输路径，能够有效地减少通信能耗，从而延长网络的生存时间。

本文主要研究无线传感器网络的网格拓扑结构，通过解决延迟约束下的中继节点选择问题，可以得到最优的中继选择，以达到减少网络通信能耗、延长网络寿命的目的。该算法主要应用于实时无线传感器网络系统，它能够在满足延迟约束的条件下给出低能耗的路由策略。

1 问题描述

无线传感器网络的网格拓扑结构是一个简单的拓扑结构，其结构示于图1。本文主要研究网格拓扑结构下无线传感器网络的低能耗路由问题。

图1 网格拓扑结构Fig 1 Grid topology structure

不同的无线传感器网络对实时性的要求是不同的。应用于环境监测、海底探测、矿山勘察等的无线传感器网络都是非实时系统，这些传感器网络的地面基站并不需要实时数据，同时，这些系统也能容忍较大的时间延迟。另一方面，监控、入侵检测、辅助导航和定位等系统却对实时性要求很高，高延时是无法容忍的。本文主要研究应用于实时系统的无线传感器网络的低能耗路由算法。在无线传感器网络中主要的延迟包含以下部分:

1）载波侦听延时:发送者监听载体是否空闲的延时。

2）传输延时:带宽约束造成的延时。

3）处理延时:节点中嵌入式芯片的计算能力决定处理延时。

4）传播延时:由距离和传播速度决定传播延时。

因此，传送一个数据包需要的时间为Tc+Tt+Tpc+Tp，其中，Tc为载波侦听延迟，Ti为传输延迟，Tpc为处理延迟，Tp为传播延迟。

首先，考虑最简单的线性拓扑结构，如图2，其中所有传感器节点在同一直线上。很显然，这类传感器网络消耗的主要能量在信息交流上，希望数据包经过多跳转发从源节点A到终节点B之间的节点时消耗最小的能量。然而，一个多跳带来额外的载波侦听延迟，传输延迟和处理延迟。在有延迟约束的实时系统中，有时会考虑牺牲一定的能量，以保证低延迟。因此，总的跳数在减少，同时每一跳的距离在变大，从而导致能耗的增加［4］，所以，需要在能耗和延时2个方面进行折衷。

图2 线性拓扑结构Fig 2 Linear topology structure

本文主要研究网格拓扑结构的无线传感器网络。针对有实时性约束的无线传感器系统，提出了一种中继节点分配的算法。根据系统的实时性约束，首先确定最优的跳数，然后在给定跳数的前提下，合理地分配中继节点，以减少系统能耗。

2 模型与假设

在如图1所示结构中，传感器节点只能向4个方向发送数据。本文中用无向图G（V，E）来描述该传感器网络，其中，V代表节点集合，E代表链路集合［5］。

在网格拓扑中，如果一个节点向另一个节点发数据，至少有一条最小能耗路径。这些路径可以由DSAP［6］协议给出。为简化问题考虑，只保留一条仅改变一次发送方向的路径。例如:在图1中，数据包由A经C发送到B就是一条仅改变一次发送方向的路径。假设传感器节点的通信范围能覆盖整个网络，从而数据包就能仅仅经过一跳最终传到目标节点。

在通信过程中，传感器节点的能耗主要包含发送能耗、接收能耗和放大器能耗。发送能耗用于保证通信模块的正常运行，接收能耗用于保证接收模块的正常运行。放大器能耗用于保证接收端的信号强度，这是由于信号在传播过程中有衰减，因此，需要对信号进行放大以补偿传播过程中的衰减。如果将发送能耗表示为Ptx，接收能耗表示成Prx，放大器能耗表示为Pamp，那么，在传感器通信过程中的能耗为

其中，Pamp，k为第k个节点的放大器能耗，那么，在一条n跳的路径中，总能耗为

通常情况下，发送能耗和接收能耗远远小于放大器能耗。一般情况下，放大器能耗可以表示为

其中，c和α均为常数，dk是第k条链路的长度。

在本文中，假设接收能耗和发送能耗均为100 nJ/bit。常数c=1，α=2。在无线传感器网络的路由协议中，希望能使Ptotoal尽可能小。

本文主要研究路由问题，MAC协议不在本文的研究范围内，因此，假设传感器网络所采用的MAC协议为ALOHA协议。

3 线性拓扑的最优跳数

线性拓扑是最简单的拓扑结构，同时也是构成网格拓扑的基础。在本节中，首先研究延时约束条件下，线性拓扑结构的中继节点选择，以实现较低的能耗。在线性拓扑中，如图2，假设A需要向B发送数据，在数据发送过程中需要经历n个节点，如果这n个节点能将A，B间的连线n等分，那么，通信过程中的能耗能达到最小值。假设数据包从A需要经过h跳到达B，A，B间的距离为l，本文希望选取h－1个中继节点将l等分为h小段，那么相对应的能耗可以表示为

通过将式（4）求导，可以很容易地得到最优的跳数。然而在有实时性要求的传感器系统中，数据包需要在规定时间内到达基站。本文在第一节中提到，数据包传输过程中的总延时可以表示为Tc+Tt+Tpc+Tp。由于信号的传播速度在理论上是光速，因此，忽略TP。同时，本文中采用ALOHA的MAC协议，因此，Tc也被忽略。从而数据包经过h跳到达基站所经历的延时可以表示为h（Ti+Tpc）。如果基站希望在时间T内收到数据包，那么延时约束可以表示为

最优的跳数就是选择合适的h，从而在满足式（5）的条件下，使得Rtotal最小。由于约束函数h（Ti+Tpc）是关于h的线性函数，所以，该优化问题等价于Karush-Kuhn-Tucker（KKT）问题。通过引入辅助变量λ，KKT问题可以表示为

通过解KKT问题，得到最优的跳数为

4 路由算法

传感器网络的路由问题就是选择一些合适的中继节点，通过多跳转发，使数据包从源节点最终到达基站。

对于线性拓扑结构，尽管能获得线性拓扑的最佳跳数，中继节点可能无法将源节点和目标节点之间的连线等分。假设源节点和基站之间的距离为l，数据包需要经过h跳到达目的地，定义一个辅助函数

其中，dij为i和j之间的欧氏距离，eij为一个0～1决策变量。eij=1 表示链路（i，j）被选中，eij=0 表示链路（i，j）未被选中。优化问题式（11）是一个0～1整数线性规划问题，通过求解该问题，可以得到相应的中继节点选择，从而解决延时约束下的路由问题。

对于网格拓扑结构，它与线性拓扑结构最大的差别在于数据包的传播方向会发生改变。因此，拐点必须作为中继节点，以保证数据包的正确发送。在第1节中，已经提到数据包至多改变传播方向一次最终到达基站，所以，只能有1个拐点。该拐点所对应 都必需取1，从而网格拓扑的路由问题可以描述为

式中i为拐点。

通过解形式如式（12）的0～1整数线性规划，便可以得到最终的路径。

5 仿真结果

在仿真实验中，网络包括100个传感器节点，这些节点被分布在10000 m×10 000 m的二维区域内。传感器节点上嵌入式芯片的CPU工作频率大约是数十兆赫。考虑到数据的操作，1 bit数据量的处理时间约为0．05 ms。因此，设Tp=0．05 ms，同时传输延迟是由信道频率决定的，即Ti=1/f。图3为时间约束1～3 s最优跳数的变化。

图3 延迟约束与最优跳数关系图Fig 3 Relationship between optimal hop number and delay constraint

一旦最优跳数确定了，路由就可以通过解决0～1整数线性规划来获得。在仿真实验中，选择一个节点作为源节点，该节点需要向基站发送一个1000 bit的数据包，在不同时间约束下，其能耗如图4所示。

6 结论

为了减少无线传感器网络的能量消耗，本文提出了一种基于网格拓扑结构无线传感器网络的新型路由算法。对于有时间限制的实时传感器系统，通过减少跳数来保证低延时。在延时约束内，本文通过解决一个KKT条件推导出最佳跳数。在得到最优跳数的前提下，本文将中继节点的分配问题转化为0～1整数线性规划问题，通过解该问题得到最终的多跳路径。仿真结果表明:本文所提出的算法是有效可行的。

图4 延迟约束下的网络能耗Fig 4 Network energy consumption vs delay constraint

［1］ Akyildiz I，Su W，Sankarasubramaniam Y，et al．Survey on sensor networks［J］．IEEE Communications Magazine，2002，40（8）:102－114．

［2］ 孙利民，李建中，陈 渝，等．无线传感器网络［M］．北京:清华大学出版社，2005．

［3］ Pottie G，Kaiser W．Wireless integrated network sensors［J］．Communications of ACM，2000，43（5）:51 －58．

［4］ Heinzelman W，Chandrakasan A，Balakrishnan H．An applicationspecific protocol architecture for wireless microsensor networks［J］．IEEE Transactions on Wireless Communications，2002，1（4）:660－670．

［5］ Merris R．Graph theory［M］．USA:Wiley-IEEE，2001．

［6］ Salhieh A，Weinmann J，Kochhal M，et al．Power efficient topologies for wireless sensor networks［C］∥International Conference on Parallel Processing，Valencia，Spain，2001:156 －163．