无线传感器网络中继节点的布局算法

王　翥，吕翠翠，王　玲

(哈尔滨工业大学(威海)信息与电气工程学院，山东威海　264209)

0　引言

无线传感器网络WSN(Wireless Sensor Networks)是多学科交叉的前沿研究热点。它是由大量具有特定功能的传感器节点通过自组织的无线通信方式，相互传递信息，协同完成特定功能的智能专用网络[1]，在环境监测、智能交通、医疗护理及工业自动化领域有广泛的应用前景[2]。

WSN由3种类型节点组成：传感器节点SN(Sensor Node)、中继节点RN(Relay Node)和Sink节点。WSN通信能力有限，通信的能量消耗通常与通信距离成指数关系，通信距离的增加会导致无线通信的能量消耗急剧增加[3]。由于SN的微型化，节点的电池能量有限，所以能量限制是整个WSN的瓶颈，它决定着网络的寿命。为节省能量，WSN应采用多跳路由的通信传输机制，即SN通过RN转发数据至sink，尽量减少单跳的通信距离，同时多跳通信也能克服远距离无线通信所遇到的一些信号传播效应问题。

RN布局是多跳路由的关键，它决定着是否可以减小网络能量消耗、延长网络寿命。文献[4-5]从理论上分析了影响RN布局的因素。文献[6]通过近似算法放置RN，使网络整体功耗达到最小。樊勇等提出一种RN多级摆放策略[7]，全巧艳等用基于正方形网格能量模型的方法均衡网络能量消耗[8]。在Lu等的文献[9]中，基于平衡所有SN和RN的功耗，作者推导出一个RN密度函数，根据密度函数在感知区域放置RN.为保证网络中放置的RN数目最少，Satyajayant 等在文献[10]提出了一种受限的RN布局构想，设定双向的通信路径。文献[11]通过在WSN中加入冗余的RN增加网络的可靠性，保证在WSN的初步设计中，每个SN到基站有k个节点不相交的路径。

上述文献研究了单约束条件下RN的布局算法，对于多约束条件下的RN，文中提出一种基于贪婪算法的RN布局方法。传统基于贪婪算法的路由协议选择离sink最近的RN作为下一跳[12]，与传统贪婪算法不同，文中制定双重贪婪准则，根据最优通信距离和多约束条件选择RN，实现WSN能量消耗小的目标。

1　网络模型

用图G表示一个WSN，定义如下：

G=(V，E)

式中：V为顶点集；E为图中边的集合。

符号定义如下：

SN集合：S0={s1，s2，…s，s2，…si，…，sn}；Si；标号为i的SN，n：SN的数目。

RN集合：R0={r1，r2，…，rj，…，rm}；rj：标号为j的RN；m：RN的数目。

v0：sink节点，v1…vn：SN，vn+1…vn+m：RN，V={v0，v1，v2，…，vn，vn+1，…vn+m}。

Cvi：节点vi的通信容量，wvi：vi的流量负荷(vi转发的流量)，RCvi：vi冗余流量。

RCvi=Cvi-wvi

节点的能量消耗分为3部分：感知、通信和数据处理。发送数据的消耗为0.38～0.7 W，接收数据的能量消耗为0.36 W，感知的能量消耗为0.02 W[13]。在100 m的网络上传输1KB数据与处理3×107条指令消耗的能量大致相等，可见在数据通信方面消耗的能量最大。文中主要考虑数据通信的能量消耗。

对于距离为d，长度为Lbit的信息，发送所消耗的能量如式(1)所示。

ETx(d，L)=(α1+α2dn1)·L

(1)

接收Lbit的信息所消耗的能量如式(2)所示。

ERx(L)=β·L

(2)

式中：α1、α2和β为参数；β为路径损耗指数；n1∈[2，4]。

SN与RN的角色不同，SN的主要任务是采集数据，对数据进行处理，然后发送数据。RN本身不采集数据，只转发SN的数据或其它RN的数据。

在满足能量的条件下，vi接收并转发的数据量分别为LRx(vi)、LTx(vi)，一般有式(3)。

LTx(vi)=LRx(vi)=L(vi)

(3)

那么消耗的总能量为E(vi)：

E(vi)=ERx〔LRх(vi)〕+ETx〔dih，LTx(vi)〕，(dih≤R)

(4)

传感器节点vj发送的数据总量LTx(vj)，因为它不转发RN和其它SN的数据，可以忽略接收数据时消耗的能量ERx(LRx(vj))，即：

ERx(LRx(Vj))≈0(J)

(5)

E(vj)=ETx(dj，k，LTx(vj))，(djk≤R)

(6)

由上述公式可知：节点的能量消耗不仅与通信距离有关，还与数据量(通信容量)有关。

在多跳路由中，通信距离取决于器件参数和实际环境参数。节点之间的最优通信距离d0由公式(7)确定[14]。

(7)

源节点与目的节点之间的距离d通常不是d0的整数倍，因此最优跳数k是最接近d/d0的整数。文中对于任意传感器节点vi，当di0≥d0时，采用多跳通信方式；当di0

2　贪婪算法

2．1贪婪算法的描述

贪婪算法是一种求最优解的简单、迅速的设计技术，它采用的是逐步构造最优解的思想，该算法容易设计、实现并且节省时间，它的典型应用是最优化问题。

使用贪婪算法解决RN布局问题需要做好3个方面：

(1)明确求解目标；

(2)分析RN布局问题所包含的约束条件；

(3)制定贪婪准则。

RN布局的目标函数用如下数学模型表示：

约束条件包括：

(1)SN数据转送次数不超过规定的上限值；

(2)通信路径满足路径“不可逆”约束条件；

(3)每个RN的数据转送率不能超过该节点所限定的最大数据转送率(通信容量)。

规定s1、s2的数据转送次数上限值为1，如图1所示。

图1　数据转送次数示意图

由图1可知：s1的数据转送次数为1，满足条件；s2的数据转送次数为2，超过1，不满足条件。

根据SN到v0的距离d以及d0，规定数据转送次数上限值。

路径“不可逆”是指满足式(7)的通信路径，如图2所示。

(7)

式中：1≤i≤n；n+1≤j≤n+m。

图2　路径“不可逆”示意图

由图2看出：

(8)

(9)

假定SN的数目、位置以及v0的位置是已知的，设置SN跳数为0，RN布局的具体步骤如下。

(1)计算si(1≤i≤n)与v0之间的距离di0，d={d10，d20，…dn0} 。

(2)当di0≤d0时，si可以与v0直接通信，删除S0中的si，然后在d中删除si对应的di0。

(3)当di0>d0时，将di0按降序排列，令nrdi是最接近di0/d0的整数，如果有多个相同的最大值(或最小值)，那么它们按SN标号由小及大的顺序依次排序。

(4)从具有最大di0值的si开始(“最远-最近”准则)，在si与v0的连线上以di0/nrdi为步长放置RN，令ri1是si的第一跳中继节点，RN_one={ri}，删除S0中的si以及d中对应的di0。

(5)对于S0中满足di0>d0的si，计算它与ri1的距离di(i1)，当满足di(i1)≤d0，假定si是ri1的子节点。

(6)每个si产生的数据量为dc，每个RN通信容量为cm，计算ri1子节点的个数，记为num(ri1)child，令Cri1=cm，wri1=dc·(num(ri1)child+1)，RCr(i1)=Cri1-wri1。

RCr(i1)≥0时，满足路径“不可逆”的si是ri1的子节点，删除S0中的si及si对应的di0。

RCr(i1)<0时，计算siri1与ri1v0的夹角θ，θ按升序排列，依次从最小θ开始(“最小”准则)，验证θ与是否是锐角，以及ri1是否满足通信容量要求。

若θ是锐角，并且ri1满足通信通量要求时，更新num(ri1child，wri1记为num(ri1)childnew、wri1new。同时删除S0中θ对应的si及si对应的di0。

num(ri1)childnew=num(ri1)childnew+1

(10)

RC(ri1=Cri1-wri1new

(11)

重复验证θ与是否是锐角，以及ri1是否满足通信容量要求。若同时满足条件，那么更新num(ri1childnew、RCr(i1)，直至θ≥90°或RCri1<0时结束。

(7)重复执行(4)～ (6)，直至d=φ。

2．2算法的复杂度

3　实验结果分析

在300 m×300 m的监测区域内放置SN和sink，用MatLAB对上述贪婪算法进行仿真，并与其它贪婪算法进行比较，通过网络的总能量消耗、RN数目评估算法的性能，实验参数如表1所示，实验结果如图3～图5所示。

表1　实验参数

其它贪婪算法在WSN应用中的贪婪准则通常为“最近准则”，即节点v选择离sink最近的RN作为下一跳[12]。

图3中A、B柱状图分别表示根据“最远-最近”准则、“最远-最小”准则时的WSN总能量消耗情况。图4中C、D柱状图分别表示根据“最远-最近”准则、“最远-最小”准则时的SN能量消耗情况。从图3、图4可知，传感器节点数目相同时，由“最远-最小”准则的贪婪算法获得的SN能量消耗、总能量消耗比一般贪婪算法获得的能量消耗小。

从图3看出，WSN总的能量消耗随SN数目的增加大致呈增加趋势。这与理论能量消耗的趋势相符。此外，还可以观察到：由“最远-最小”准则的贪婪算法得到的总能量消耗较小。图5中a、b曲线分别表示表示“最远-最近”准则、“最远-最小”准则的RN数目随SN数目的变化，从图5可知两曲线的趋势大体一致，即RN数目随SN数目的增加而增加。

图3　WSN的能量消耗

图4　SN的能量消耗

图5　RN数目的比较

4　结束语

文中对WSN中继节点布局问题进行研究，提出传感器节点的数据转送次数、数据传输路径“不可逆”等约束条件。根据节点之间的最优通信距离设置满足上述条件的“最远-最小”贪婪准则。在传感器节点的数目相同的情况下，与其它贪婪准则的贪婪算法比较，文中提出的“最远-最小”贪婪准则的贪婪算法WSN整体的能量消耗小。

参考文献：

[1]AKVIDIZ I F SU W，SANKARASUBRAMANIAM Y，et al．Wireless sensor network：a survey．computer Networks，2002，38：393-341．

[2]陈林星．无线传感器网络技术与应用．北京：电子工业出版社，2009：1-23．

[3]王殊．无线传感器网络的理论及应用．北京：北京航空航天出版社，2007：2-10．

[4]VALLIMAYIL A，DHULIPALA V R S，RAGHUNATH K M K，et al．Role of relay node in Wireless Sensor Network：A survey．2011 3rd International Conference on Electronics Computer Technology (ICECT)，2011，5：160 -167．

[5]HAN X F，CAO X，ERROL L L，et al．Fault-Tolerant Relay Node Placement in Heterogeneous Wireless Sensor Networks．IEEE Transactions on Mobile Computing，2010，9(5)：643-656．

[6]陆克中，刘刚，陶耀东，等．无线传感器网络中继节点的最小功耗布置算法．小型微型计算机系统，2011，32(6)：1035-1040．

[7]樊勇，张晓彤，万亚东，等．实现能量均衡消耗的传感器网络节点摆放策略．计算机工程，2007，33(16)：11-13．

[8]全巧艳，邓宗白．基于正方形网格能量模型的能量均衡策略．工业仪表与自动化装置，2010(4)：7-9．

[9]LU K，LIU G，MAO R，et al．Relay node placement based on balancing power consumption in wireless sensor networks．Wireless Sensor Systems，2011，1(1)：1-6．

[10]MISRA S，HONG S D，XUE G L，et．al．Constrained Relay Node Placement in Wireless Sensor Networks：Formulation and Approximations．IEEE/ACM Transactions on networking，2010，18(2)：434-447．

[11]SITANAYAH L，BROEN K N，SREENAN C J．Fault-Tolerant Relay Deployment for k Node-Disjoint Paths in Wireless Sensor Networks．2011 IFIP Wireless Days，WD 2011，Niagara Falls，2011：1-6．

[12]吴谋，张晴．自适应的移动Ad hoc网络贪婪地理路由协议．计算机应用研究，2010，27(8)：3124-3126．

[13]RAGHUNTHAN V，SCHURGERS C，PARK S，et al．Energy-aware wireless microsensor networks．IEEE Signal Processing，2002，19 (6)：40-50．

[14]BHARDWAJ M，GARNETT T，CHANDRAKASAN A P．Upper Bounds on the Lifetime of Sensor Networks．Proc．IEEEICC2001，2001：785-790．