节点位置固定的线性无线传感器网络节能路由*

2014-09-13孟庆丰

计算机工程与科学 2014年11期

关键词：生命周期路由分组

王楠，孟庆丰

(西安交通大学润滑理论与轴承研究所，陕西西安 710049)

节点位置固定的线性无线传感器网络节能路由*

王楠，孟庆丰

(西安交通大学润滑理论与轴承研究所，陕西西安 710049)

无线传感器网络节点一般采用电池供电，能量非常有限，因此提高网络能量效率、最大化网络生命周期成为亟待解决的重要问题。线性无线传感器网络在某些实际应用中，由于监测环境和对象的特殊性，监测点位置往往是事先确定的，并非随机分布，故现有的线性路由和变距离节点布置方案应用性受限。针对这一问题，提出了一种等距离分组多跳路由，建立了其能耗数学模型，得到了网络平均能耗与网络长度、节点数和分组数的数学关系，并给出了最小网络平均能耗下的分组数求解方法，最后用Matlab软件仿真分析。结果表明，与单跳、多跳、分簇多跳三种常见路由相比，等距离分组多跳路由由于没有簇头，因此具有最小的网络平均能耗和最大的网络生命周期。

线性无线传感器网络；节能路由；网络平均能耗；网络生命周期

1 引言

近年来，线性无线传感器网络逐渐广泛地应用在野外油气管道、列车轴承监测、河流、矿井及交通线监测等领域。由于在大部分情况下，网络节点都采用电池供电，无线传感器网络的节点能量、计算资源、通信能力和节点可靠性等十分有限，因此如何充分利用节点能量、延长网络寿命已成为当前研究的重要课题之一[1]。

关于线性无线传感器网络的网络寿命优化及节能路由，此前已有学者对其作了研究。文献[1]提出了一种通过线性规划和动态路由更新来延长网络寿命的最优算法。文献[2]建立了多跳线性网络拓扑结构下的等间距和优化间距的网络能量模型，求出了网络最小能耗下的节点距离公式。文献[3]为了平衡网络中各节点能耗，令每个节点耗能相等，得到了节点分布规律，并与节点均匀分布和文献[2]中的节点布置方案进行了对比。文献[4]研究了给定节点数如何确定最优节点间距及给定节点间距如何确定节点密度两种情况，求出了最优节点间距和节点密度公式。文献[5]以货运列车监测为背景，提出了两种路由MERR(Minimum Energy Relay Routing)和AMERR(Adaptive MERR)，建立了泊松能量模型，得到了最优跳数及特征距离。文献[6]研究了跳数和网络能耗之间的关系，并通过对线性网络的分析，建立了单跳和多跳路由的应用准则。文献[7]采用提出的节点密度公式非均匀布置节点，并与均匀布置节点方案进行了比较。文献[8]为了监测野外油气管道，设计了一种线性网络协议WP-LTS(WSN Protocol for Linear Topological Structure)。文献[9]提出了一种高效节点部署算法，求出了最佳工作点数，最佳中继节点部署方案和最优传输距离。

上述文献中，为了使网络能耗最小，都假定节点随机布置，经过一系列优化算法，得到了最优跳数及变距离节点布置方案。而线性无线传感器网络在实际应用中，往往会出现以下情况：由于监测环境或对象的特殊性，网络中某段区域甚至于整个网络的监测点事先已经确定，因而节点位置是固定的，并非随机分布。此时为了节省网络能量、延长网络生命周期，现有的线性路由及变距离节点布置方案并不适用，因此需要重新考虑路由策略，寻求新的路由算法。为此，本文提出了等距离分组多跳路由GMRED(Grouped Multi-hop Routing algorithm based on Equal Distance)，并建立了其能耗数学模型。最后应用Matlab软件，在近似实际应用的仿真环境下，分别从三个方面(即网络单节点能耗、网络平均能耗和网络生命周期)将等距离分组多跳路由与单跳路由SR(Single-hop Routing Algorithm)、多跳路由MR(Multi-hop Routing algorithm)、分簇多跳路由CMRED(Clustering Multi-hop Routing algorithm based on Equal Distance)三种常见路由比较，并详细分析了仿真结果。

2 问题描述与网络模型

线性无线传感器网络的拓扑结构是近似直线的，在实际应用时，若监测点事先确定，则节点位置固定不变，此时网络长度由节点数目决定。由于某些监测环境或对象，例如油气管道、列车、矿井和交通线等是分段的，且各监测点分别位于每段区域的相同位置，因此区域间各节点距离相等。而在已有文献中，不仅假定节点随机分布，且仿真时大部分中间节点只作为中继节点转发数据(实际上，网络中的各节点还需承担采集与处理数据的任务)，这些假设都与本文讨论的情况是不相符的。另外，文中建模时还考虑了节点在空闲时间的能耗。本文建立的线性无线传感器网络模型及节点具有以下特征：

(1)网络拓扑结构基本保持线性，容错性较好；若有节点失效，则网络立即启动路由发现和路径选择机制，寻找临近节点，或直接将数据发至基站。

(2)节点是同构的，即每个节点都有唯一标识，在一个网络周期内节点都需要将数据传至基站；节点持续监测，并以恒定速率发送数据；节点数据传输过程不考虑冲突和重传。

(3)节点知道其它节点的位置信息，具有和基站通信的能力，但不具有移动性；所有节点初始能量相等，能量主要消耗在数据发送与接收过程中；节点既要采集与处理数据，又要转发数据。

综上所述，现在要解决的问题是：在节点位置固定且确保数据正确采集、处理和传输的应用环境下，如何进行路径选择才能让网络中各节点的能耗尽量均衡、网络平均能耗较低、网络生命周期最长。

3 等距离分组多跳路由与能耗模型

无线传感器网络路由协议的好坏对网络能量效率和网络寿命而言，至关重要。路由协议对网络能耗的影响主要有以下几个方面[10]：路由机制、路径选择和路由度量。路由机制表示网络采取的信息处理模式，是先应式(路由表驱动)还是反应式(按需)。路由度量表示采取什么评价标准来选择最优路由协议，例如：最小跳数、最小能耗等。本文主要研究路由协议中的路径选择算法，路由度量则采用网络单节点能耗和最小网络平均能耗。

上一小节已经说明，某些监测对象是分段的，且监测点固定，因此节点位置固定，区域间各节点间距相等。为讨论方便，网络各节点采取均匀布置；与实际应用对象类似，所有网络节点分为若干组(各组节点数相同、每组之间的距离相等)，等距离分组多跳路由如图1所示。每组节点分别向下一组相应节点以相同距离d进行数据传输，距离基站最近的一组(第一组)节点最终将所有数据传至基站；但第一组节点传输距离各不相同(单跳)。网络运行过程中，如有节点失效，则启动路由发现及路径选择机制，选择临近节点继续完成任务。不难看出，本路由可以看成多个多跳路由的穿插组合，因此没有簇头，不会有簇头耗能过大而导致节点间能量极不均衡的情况出现。网络生命周期定义为从网络启动直至网络中不再有节点有能力向基站发送数据为止。

Figure 1 Grouped multi-hop routing algorithm based on equal distance图1 等距离分组多跳路由

图2是网络能量模型[3]，αtx、αrx分别表示节点传输一位数据的能耗；ξ表示传输放大器能耗；γ表示路径损耗指数(2≤γ≤6)，若网络节点处于非常好的可视通路(无阻碍或较少阻碍)，γ=2；若节点位于城区，γ=6；d表示传输数据两节点之间的距离；Etx和Erx分别表示节点发送或接收k位数据所需能量。由图2可知，当其他参数不变时，节点发送数据的能耗与数据量k和传输距离d有关，而节点接收数据的能耗只和数据量有关。由图2的能量模型可以得到等距离分组多跳路由的网络平均能量数学模型。模型建立时，还考虑了节点的初始能量和空闲时间能耗问题。设节点处理数据速率为P，空闲时间为Tid，则节点空闲时间能耗可表示为：Eid=cParxTid(i)，c=0.2。表1为此次建模和仿真中用到的一些参数。

Figure 2 Energy model图2 能量模型

ParametersValue(Unit)InitialenergyofnodeE02.7kJ(0.5Ah,1.5V)DatapacketlengthB512(bits/packet)CycletimeTd130(s)DataprocessingrateofeachnodeP1(packets/s)NetworklengthL1620(m)NumberofnodeN60Energyconsumptionwhennodere-ceivesadatabitarx50(nJ/bit)Energyconsumptionwhennodesendsadatabitatx50(nJ/bit)Pathlossindexγ(2≤γ≤4)2EnergyconsumptionofRFamplifierξ10(pJ/bit/m)

假定各节点采集相同长度的数据，采用等距离分组多跳路由的网络平均能耗模型建立过程如下：

(1)求出网络中各节点能耗。

第一组各节点能耗：

(1)

除第一组外各组节点能耗：

(2)

(2)求出网络平均能耗。

由于整个路由可以看成多个多跳路由的穿插组合，先求出每个多跳路由各节点能量和，如式(3)所示。

(3)

由式(3)可得网络平均能耗(P=1，Ne个多跳路由，Ne=N/M)如式(4)所示。

(4)

由式(4)可知，网络平均能耗是网络长度L、节点数N及分组数M的函数。假定N已确定，则L也为常量，则网络平均能量只和M有关。容易证明，式(4)有极小值。将Eave对M求导并令其为零，整理后可得式(5)。

(5)

式(5)有两种方法求解：一是用一元三次方程求解公式；二是采用下述方法：将式(5)适当变换，设定两个函数y1、y2，如式(6)和式(7)所示。

(6)

(7)

求以上这两个函数的交点并作图，此外，作出与式(4)对应的图像用以辅助分析。总之，代入表1各仿真参数，可求得最小平均能耗下的最佳网络分组数M。图3a为方法二求解M的函数曲线图，图中有两个交点M1、M2，由此说明式(5)在正实数范围内有两个解。图3b为网络最小平均能耗Eave随M的变化趋势，可见式(4)是有最小值的；同时参照图3a结果可知，M=20时，网络最小平均能耗Eave(min)=1 184.5 μJ。

Figure 3 Group number and average energy of network图3 分组数和网络平均能量

等距离分组路由算法可描述如下：

输入：L、N、B等式(1)～式(5)中要用到的参数(表1)；Li为网络各节点生命周期；Ni为网络中活动节点数；Esi为各节点剩余能量；1≤i≤N。

步骤1求解式(5)，得到最佳分组数M；代入式(4)得到网络最小平均能量；所有节点分为M组，第一组节点按距离j*L/N，1≤j≤N/M传输数据；其它组节点按距离L/M传输数据，网络启动。

步骤2求解式(1)和式(2)，得到各节点在一个周期内能耗Egi；计算各节点剩余能量Esi=E0-Egi；转至步骤3。

步骤3若Esi不为零，则Li+1，转至步骤2；若Esi为零，则此节点失效，启动路由发现与路径选择，寻找临近节点继续任务，Ni-1；若Ni为零，即网络失效，同时得到网络生命周期Max(Li)，算法结束。

4 仿真结果与分析

图4为应用等距离分组多跳路由时，网络各节点在单周期内(Td=130 s，见表1)的能耗分布图。为了比较，还给出了分组数目分别为6和10时的各节点能耗。由图4可见，整个图除了第一组节点外，其余呈阶梯状，每个台阶表示同一组节点，其能耗相同。第一组节点由于是单跳，传输距离各不相同，而节点能耗与传输距离密切相关，因此曲线形状与其它节点不同(与图6中单跳路由曲线相同)。

与其他两种分组情况相比，分组数目为20时，网络中大部分节点能耗处于较低水平；但第一组各节点能耗较大，这是由于每组节点转发的数据量随着分组数目的增加而增大的原因。

Figure 4 Energy consumption distribution of network node图4 网络各节点能耗分布

Figure 5 Normal routings图5 常见路由

图5分别为常见单跳、多跳与分簇多跳路由，各路由节点亦为均匀布置。图6为网络应用这几种路由时，各节点在一个网络周期内的能耗分布。为了比较，仿真环境和条件与等距离分组多跳路由相同，分簇多跳路由的分组数和最小平均网络能耗下的等距离分组多跳路由分组数相同。另外，还建立了单跳、多跳与分簇多跳路由的网络平均能量模型，模型的建立方法与过程和上一小节中等距离分组多跳路由类似。比较图4和图6可知，与等距离分组多跳路由相比，单跳和多跳路由节点能耗随着节点与基站距离的增大而分别单调增加和减小，各节点的能耗分布极不均衡。单跳路由适合小范围监测[11,12]，若在大范围使用，将导致节点在未完成监测任务前，由于能量耗尽而无法继续监测，称为监测盲区SBZ(Sensing Blind Zone)。多跳路由的节点能耗虽和单跳路由一样呈单调变化，但变化趋势要平缓得多；多跳路由用于监测大面积区域[12]，但离基站近的节点能量消耗大，容易引起网络中心数据黑洞DBHLC(Data’s Back Hole in Logic-topology Center)，吞噬数据，使数据无法传输到节点。分簇多跳路由在每一组内是单跳传输，组间是多跳传输，但由于大量数据发至簇头，通过簇头最终将数据传到基站，簇头消耗的能量远大于其它节点(见图6)，更容易导致节点能量快速耗尽而使网络失效。

Figure 6 Energy consumption of network node for various routing图6 不同路由网络节点能耗

与上述三种路由相比，等距离分组多跳路由没有簇头，且数据在每组节点间依次传输，每组节点能耗相等；距离节点最近的一组采用单跳传输，即“小范围监测”，其它组间数据传输采取组合多跳，则为“大面积区域监测”。由于更好地结合了单跳和多跳路由的各自特点，故网络平均能耗较小、网络生命周期更长。

图7为不同路由的网络平均能耗Eave比较，当分组数目为20时，应用等距离分组多跳路由，网络平均能耗最小，而其他分组情况下，网络平均能耗要大一些。单跳路由网络平均能耗最大，多跳和分簇多跳路由网络能耗则稍低，分簇路由网络能耗低于多跳路由。由以上分析可见，等距离分组多跳路由优势明显，网络平均能耗分别是单跳、多跳和分簇多跳路由的25.6%、71.7%和88.7%。

Figure 7 Average energy of network for various routing图7 不同路由网络平均能量

图8为各种路由情况下，网络的生命周期比较。显而易见，应用等距离分组路由时，网络生命周期最长，单跳路由网络生命周期最短。虽然多跳路由比分簇多跳路由网络平均能耗大，但由于簇头的耗能太大，节点能耗极不均衡，故最终分簇多跳路由网络生命周期小于多跳路由。经过计算，等距离分组多跳路由的网络生命周期分别是单跳、多跳和分簇多跳路由的8、1.9和2.8倍。

Figure 8 Lifetime of network for various routings图8 不同路由网络生命周期

5 结束语

本文从应用角度出发，提出了一种针对节点位置固定情况下的线性无线传感器网络节能与延长网络生命周期的解决方案——等距离分组多跳路由。由于没有簇头，且较好地结合了单跳和多跳路由各自的特点，因此该路由可大幅延长网络寿命，提高网络能耗效率。在建立的网络平均能量数学模型的基础上，用Matlab软件实现仿真，并与常见单跳、多跳和分簇多跳路由比较分析。通过对网络各节点能耗、网络平均能耗和网络生命周期三方面的比较，结果表明，等距离分组多跳路由具有最小的网络平均能耗和最长的网络生命周期，其网络平均能耗分别是单跳、多跳和分簇多跳路由的25.6%、71.7%和88.7%；而网络生命周期则分别是单跳、多跳和分簇多跳路由的8、1.9和2.8倍。

[1] Qu Jia-qing, Zhang Shu. Dynamic routing algorithms optimizing lifetime of wireless sensor networks[J]. Transducer and Microsystem Technologies, 2009, 28(12):57-63.(in Chinese)

[2] Shelby Z, Pomalaza-Raez C, Karvonen H, et al. Energy optimization in multihop wireless embedded and sensor networks[J]. International Journal of Wireless Information Networks, 2005, 12(1):11-21.

[3] Hossain A, Radhika T, Chakrabarti S, et al. An approach to increase the lifetime of a linear array of wireless sensor nodes[J]. International Journal of Wireless Information Networks, 2008, 15(2):72-81.

[4] Hong Li,Xu Shun-jie.Energy-efficient node placement in linear wireless sensor networks[C]∥Proc of International Conference on Measuring Technology and Mechatronics Automation, 2010:104-107.

[5] Zimmerling M, Dargie W, Reason J M. Localized power-aware routing in linear wireless sensor networks[C]∥Proc of the 2nd ACM International Workshop on Context-Awareness for Self-managing Systems, 2008:24-33.

[6] Wang Jin,Niu Yu,Cho J,et al.Analysis of energy consumption in direct transmission and multi-hop transmission for wireless sensor networks[C]∥Proc of the 3rd International IEEE Conference on Signal-image Technologies and Internet-based System, 2007:275-280.

[7] Lu Ke-zhong, Liu Ying-ling. Deploying nodes scheme in line wireless sensor networks[J]. Computer Applications, 2007, 27(7):1566-1568. (in Chinese)

[8] Hu Yan-hua.Research and design of protocol for wireless sensor networks used in monitoring of oil and gas pipelines in field [D]. Nanjing:Nanjing University of Science and Technology, 2007. (in Chinese)

[9] Liu An-feng, Nie Hong-wei, Wu Xian-you, et al. Optimization deployment algorithm for network efficiency of linear wireless sensor networks[J]. Computer Science, 2009, 36(11):83-87. (in Chinese)

[10] Yang Guang-song, Shi Jiang-hong, Chen Hong-xia, et al. Energy consumption factors analysis and simulation of wireless sensor networks[J]. Journal of Jimei University, 2008, 13(2):141-145. (in Chinese)

[11] Cheng Peng,Chuah C N,Liu Xin.Energy-aware node placement in wireless sensor networks[C]∥Proc of Global Telecommunication Conference, 2004:3210-3214.

[12] Zhang Zhi-dong, Sun Yu-geng, Liu Yang, et al. Energy model in wireless sensor networks[J]. Journal of Tianjin University, 2007, 40(9):1029-1034. (in Chinese)

附中文参考文献：

[1] 曲家庆, 张曙. 优化无线传感器网络寿命的动态路由算法[J]. 传感器与微系统, 2009, 28(12):57-63.

[7] 陆克中, 刘应玲. 一种线型无线传感器网络的节点布置方案[J]. 计算机应用, 2007, 27(7):1566-1568.

[8] 胡炎华. 野外油气管道监测的无线传感器网络协议研究与设计[D]. 南京:南京理工大学, 2007.

[9] 刘安丰, 聂红伟, 吴贤佑, 等. 基于网络效率的线性无线传感器网络优化部署算法[J]. 计算机科学, 2009, 36(11):83-87.

[10] 杨光松, 石江宏, 陈红霞, 等. 无线传感网中能耗因素的分析与仿真[J]. 集美大学学报, 2008, 13(2):141-145.

[12] 张志东, 孙雨耕, 刘洋, 等. 无线传感器网络能量模型[J]. 天津大学学报, 2007, 40(9):1029-1034.

WANGNan,born in 1983,PhD,lecturer,CCF member(E200029347G)，his research interests include measurement technology and application of wireless sensor networks, mechanical equipment state monitoring and fault diagnosis.

孟庆丰(1959),男,河北海兴人，博士，教授，研究方向为机械设备状态监测和故障诊断、信号处理理论及方法。E-mail:qfmeng@mail.xjtu.edu.cn

MENGQing-feng,born in 1959,PhD,professor,his research interests include mechanical equipment state monitoring and fault diagnosis, theory and method of signal processing.

Energyefficientroutingforlinearwirelesssensornetworksbasedonfixednodelocation

WANG Nan，MENG Qing-feng

(Theory of Lubrication and Bearing Institute,Xi’an Jiaotong University,Xi’an 710049,China)

The energy of Wireless Sensor Networks (WSNs) is very limited because battery is used for power supply in nodes normally.Therefore, the key issue that needs to be solved,is to improve the energy efficiency and prolong the lifetime of networks.In some practical applications of linear WSNs,due to the particularity of the monitoring environment and objects,the location of the monitoring points that is not in random distribution is fixed in advance, and this results in the limitation of applicability for the existing linear routing and the nodal arranging scheme with variable distances. Therefore, a grouped multi-hop routing algorithm based on equal distance, named GMRED, is proposed.The energy consumption mathematical model of the networks is constructed, and the network average energy is determined by the network length,the number of nodes and the groups. How to solve the problem of the group numbers when the network has minimum average energy is discussed. Finally, the Matlab software is used for simulation and analysis.The results show that,compared with the single-hop routing algorithm,the multi-hop routing algorithm,and the clustering multi-hop routing algorithm,the GMRED has the minimum average energy consumption and the maximum network lifetime because it has no cluster head.

linear wireless sensor networks；energy efficient routing；average energy consumption of network；lifetime of network

1007-130X(2014)11-2087-07

2013-05-20;

：2014-09-10

国家自然科学基金资助项目(50875196,51175049,51275380)

TP393.02

：A

10.3969/j.issn.1007-130X.2014.11.006