節點位置固定的線性無線傳感器網絡節能路由*

王 楠，孟慶豐

(西安交通大學潤滑理論與軸承研究所，陜西 西安 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

王楠(1983),男,陜西渭南人，博士，講師，CCF會員(E200029347G)，研究方向為無線傳感器網絡測量技術及應用、機械設備狀態監測和故障診斷。E-mail:heroyoyu@126.com

通信地址：710049 陜西省西安市碑林區咸寧西路28號西安交通大學潤滑理論與軸承研究所

Address:Theory of Lubrication and Bearing Institute,Xi’an Jiaotong University,28 Xianning Rd West,Beilin District,Xi’an 710049,Shaanxi,P.R.China