無線傳感器網絡中帶有移動匯點的能量高效的數據收集協議*

汪林云，劉文軍

(1.溫州大學城市學院，浙江 溫州325035;2.同濟大學電子與信息工程學院，上海201804;3.蘇州大學計算機科學與技術學院，江蘇 蘇州215006)

近年來無線傳感器網絡(WSN)已成為軍事、健康護理、智能家居、目標追蹤、環境監測和預報等眾多應用領域吸引人的技術。針對傳感器網絡特點，設計和部署一個成功的網絡需要考慮包括部署機制、能量保存、動態環境下的路由在內的眾多細節問題。特別地，能量效率已成為WSN協議設計最基本的問題之一?，F存平衡能量消耗的解決方案，如部署優化［1］，拓撲控制［2］，數據匯聚［3］等，大多采用多跳路由中繼數據。多跳路由的缺點是容易導致網絡節點，特別是匯點附近的節點，因轉發其他網絡節點的數據快速耗光能量。

由于傳感器網絡在資源上受限的固有特征，分簇算法產生的層次型拓撲具有很多優點，如可以減少通信負載、降低節點能耗、平衡負載、延長網絡壽命和增強網絡的可擴展性等，因此，分簇算法在大規模無線傳感網絡的使用非常普遍［4－5］。

最近的研究表明，在網絡中引入移動元素(ME)可以顯著提高能量效率、連通性和可靠性［6－9］。WSN固有的多對一通信模式使得距離匯點近的節點負載比其他節點更重，容易遭受過早的能量耗盡。移動匯點(MS)可以有效解決該問題，它們在網內移動可以使節點能量消耗更加均衡。此外，由于匯點可以和網內節點以單跳模式進行通信，不僅減少了信道的競爭和沖突，提高了通信質量，也在一定程度上避免了消息丟失情況的發生。

1 現存相關算法分析

在傳感器網絡中引入移動匯點且其狀態可控時，可以通過合理選擇移動匯點的運動軌跡來減少數據收集延遲，提高系統工作效率。不難得出結論，移動匯點和普通數據收集節點之間直接接觸的數據收集問題可以等價于NP完全的旅行售貨商問題(TSP)。Nesamony等人［10］將匯點旅行問題形式化為TSP的變體，稱為具有鄰域關系的旅行售貨商問題(TSPN)，匯點需要訪問每個節點的鄰域恰好一次。移動匯點逐步到達每個節點的通信范圍內，從而可以充分地接受到來自傳感節點上的感測數據。

網絡輔助的導航(NAN)問題［11］旨在尋找一個MS的移動軌道使得所有節點以單跳方式可達。可以通過創建一個稱為導航代理(NA)的邏輯覆蓋拓撲達到該目標。如果定義一個跳限因子k，使得數據可以在k跳內被轉發則NAN進一步擴展為網絡輔助的數據收集(NADC)問題［12］。易見當 k=1 NADC問題對應 NAN問題。類似地，TRACK［13］采用支配集CDS構建骨干網，對構建的骨干網采用一種分布式算法產生一棵最小生成樹MST［14］，在MST的基礎上將每條邊看作兩條邊，尋找一條哈密頓圈HC作為移動匯點的軌跡。該機制的缺點是生成的軌跡仍然較長，仍可能導致數據溢出等問題的發生。

綜合利用分簇和移動匯點技術，本文提出一種能量高效的無線傳感器網絡數據收集協議。協議首先依靠分簇機制生成通信骨干網，對骨干網采用一種適合資源有限的無線網絡的分布式MST算法獲得其最小生成樹，在此基礎上借助解決TSP問題的思想，構建一條路徑最短的MS移動軌跡。該運動軌跡上MS和每個簇以單跳方式通信，增強了通信信道質量，解決了熱點等問題的發生。

2 系統模型

2.1 網絡模型

考慮由N個傳感器節點均一地部署在廣闊區域(如方形)上進行連續的環境監測應用環境。為了研究問題的方便，首先對傳感器節點和潛在網絡模型進行假定:

(1)節點周期性監測環境數據，計算和存儲功能有限，節點對地理位置信息不敏感，可以工作在休眠和喚醒模式以節省能量;

(2)移動匯點MS以不確定性模式在網絡內以一定速率移動，其能量和計算能力不受限制;

(3)MS和骨干節點在通信范圍內進行數據傳輸，不發生數據丟失情況;

(4)網絡為同構的分層網絡模型，通信鏈路是對稱的，通信范圍內的節點和MS單跳通信，全網單跳通信;

(5)假定存在某種數據匯聚機制以節省網內節點能量。

對通信能量損耗的評估使用一種簡化的模型［15］。依據發送器和接收器之間距離的不同，使用自由空間(d2功率損耗)和多徑衰落(d4功率損耗)通道模型。在距離d上傳輸l位的包所花費能量的計算公式為:

其中，Eelec表示節點發射電路的損耗。若傳輸距離小于閾值d0，則功率放大損耗采用自由空間模型，否則采用多路徑衰減模型。εfs，εmp分別為這兩種模型功率放大所需的能量。接收消息花費的能量計算公式為:

2.2 問題和需求

一般地，一個好的分簇模式應滿足以下需求:

(1)采用算法復雜度可接受的分布式分簇機制，即算法時間和消息復雜度是高效的，分簇效果盡可能均勻以平衡能量的消耗;

(2)分簇算法執行的結果使得每個節點要么是簇首，要么是普通成員節點。

基于分簇的骨干網形成后，簇首間的通信可以抽象為帶權圖G(V，E，c)。一條邊e=(u，v)存在當且僅當u在v的傳輸范圍且v的剩余能量可以負擔所需通信費用。頂點集V代表簇首集，邊集E代表通信鏈路集，對每條邊e∈E有通信代價c(e)＞0。

給定一個簡單連通無向圖G，圖G的生成樹T是一棵連接所有頂點子圖的樹。一棵最小生成樹(MST)或最小帶權生成樹是一棵生成樹T使得∑(u，v)∈Td(u，v)最小，此處 d(u，v)是邊(u，v)的長度，定義為u和v兩點之間的歐氏距離。簇首的MST是連接所有簇首且邊的通信代價之和最小的一棵樹。

SE通過一條確定的路徑逐次訪問每個節點來遍歷整個網絡。一個圈被稱為哈密頓的，如果V中的每個頂點恰好訪問一次。已知旅行售貨商問題(TSP)的目標是尋找最小費用的哈密頓圈HC(Hamiltonian Cycle)。該問題是NP完全的，無法尋找多項式時間算法解決一般性的TSP問題。考慮放松條件為允許多次訪問相同頂點。借助該抽象模型原問題轉化成尋找滿足如下目標的最優移動軌跡:

(1)MS移動通過所有簇首，以單跳方式進行通信。特別地，MS可根據需要僅通過部分核心簇首，簇首間以有限跳數進行多跳方式通信;

(2)MS移動軌跡構建算法是分布式且高效的，構建的移動軌跡盡可能短，以防止數據溢出現象的發生。

3 系統設計

數據收集協議主要分為基于分簇的骨干網構建和MS移動性軌跡確定兩個階段。對骨干網的構建，采用一個消息復雜度為O(n)的分布式分簇算法。對MS的移動軌跡確定采用一種最初用于解決TSP問題的常量近似因子1.5的改進的分布式算法。

3.1 分布式分簇機制

網絡部署階段，基站(BS)以某種功率水平向網內所有節點廣播HELLO_MES消息。收到消息后每個節點檢驗自身是否是候選簇首。每個候選簇首基于收到的信號強度計算其到BS的近似距離，然后執行分布式簇首競選算法，該算法的主要思想由Chen等人提出用于解決非均勻分簇問題［4］，簇首競選主要基于候選簇首的剩余能量，簇的半徑為常量R，該參數可基于特定需要進行調整。

(1)分簇前BS以某種概率隨機選擇預定義數量的候選簇首來競爭最終的簇。為了節省能量，非候選簇首保持休眠狀態直至簇首選擇階段結束為止。

(2)每個候選簇首廣播一條包含了半徑和剩余能量的簇首競選消息COMPETE_CH。每個控制消息的廣播半徑是Rmax=2R，所以候選簇首ci可以聽到來自于相鄰簇首集合ci·SCH的所有消息。構建SCH結束后，每個候選簇首檢驗其SCH并確定是否可以作為簇首。如果構建的SCH為空，則候選簇首立刻變為最終簇首。一旦ci發現其剩余能量高于SCH中的有的節點，它將贏得競選。如果cj屬于ci·SCH且ci收到來自于cj的FINAL_CH消息，則ci放棄競選過程。

(3)所有的最終簇首確定后，BS記錄它們關于剩余能量、標識ID、距離等相關信息，用于后續階段(移動路徑選擇)。之前休眠的節點被喚醒，每個節點基于收到的信號強度加入最近的簇并通過發送JOIN_CLU消息通知簇首。簇首建立一個TDMA時序并傳輸給簇內節點。簇內節點收到該TDMA時序后，分簇階段完成。

在分簇算法的執行過程中，每個候選簇首發送一個COMPETE_CH消息。如果該節點變為簇首則廣播一個FINAL_CH消息來聲明其贏得競選或者廣播一條QUIT_ELECT消息予以退出。每個簇首廣播一條CH_ADV消息，而每個普通節點則廣播一條JOIN_CLU消息?；谝陨戏治?，每個節點的消息復雜度為O(1)。分簇階段中，總的消息開銷為2M+Nc+N－Nc=O(N)，此處N為網絡規模，M為候選簇首數，Nc是最終簇首數。

網絡中的任意節點存在三種狀態:RegularNode，CandidateCH和FinalCH。對任意的候選簇首ci如果它沒有任何相鄰節點，則ci立刻變為最終簇首。否則ci要么變為最終簇首要么變為普通節點，不存在其他情況。因而，分簇算法執行后，每個節點要么是簇首要么是普通節點。每個普通節點屬于一個簇，且在每個競選范圍內僅存在一個簇首。

3.2 構建MS行動軌跡

MS移動軌跡的構建首先需要在骨干網基礎上生成MST。本文采用由Khan等人提出的稱為最近鄰居樹(NNT)的分布式算法生成，記為 NNT_MST［16］。所有節點具有唯一的構成有序集的ID，每個頂點v獨立執行如下過程:選擇唯一的等級v.rank，連接到最近的節點 w 使得 w.rank＞v.rank，即添加一條邊(w，v)到NNT中。相對于消息最優的GHS算法，該算法產生的MST所消耗的能量顯著降低。

在不考慮移動匯點MS移動速度、網絡不穩定性等因素對數據傳輸的影響，MS的移動性可以僅通過其移動軌跡進行刻畫，如果在MST中將地理位置靠近的奇數度頂點相連使其構成偶數度，則生成的HC長度明顯縮短。獲得MS移動軌跡具體過程如下:

(1)變量初始化，令 G=(V，E)，V=VCH，E=EMST+EREG，即圖G的頂點集由簇首節點構成，邊集由MST中的邊EMST和簇首間存在通信鏈路的所有邊EREG構成;令S為最小生成樹T中奇數度頂點集合。

(2)對S中的每個頂點v，如果其度為奇數，則在EREG中尋找一條最小代價邊，使v和通過該邊相連的另一端頂點w都構成偶數度頂點，并將該邊添加到T中。該步驟執行的結果是形成圖G的生成子圖G'，該圖包括了所有簇首頂點且每個頂點都具有偶數度。

(3)MS從圖G'中的任意頂點開始訪問網絡，在移動過程中MS記錄它所經過的簇首相關信息(位置、節點鄰居和已訪問的鄰居等)。若節點有多個鄰居，則隨機挑選一個進行訪問，并使用布爾變量對訪問過的邊進行標記;若節點的所有鄰居均訪問完畢，則返回到最近的奇數度頂點。重復以上過程，直至網絡中所有的節點訪問完畢，返回到出發點。

圖1(a)顯示了利用分布式分簇算法生成的12個簇，每個簇內包含一個簇首節點。利用分布式最小生成樹算法生成MST如實線所示，虛線表示簇首之間存在通信鏈路。圖1(b)圖示了移動匯點的移動軌跡。初始時MS從節點v1出發，然后依次選擇鄰居 v2，v3，v4，v5，在節點 v5處，(v3，v5)不是生成樹的邊，但二者存在通信鏈路，且兩個節點的鄰居數均為奇數，因此v5選擇v3作為鄰居。類似的情況存在于v9和v10，v8和v11之間。當MS行走到節點v6處，網絡中距離v6最近的奇數鄰居節點為v1，此時，MS從v6返回到初始點v1，完成對整個網絡骨干節點的訪問，移動過程中MS以一跳方式收集網絡中所有節點的信息。MS可以在一次移動后獲得網絡的整體信息，從而可以借助這些信息對整個系統進行全局優化。

圖1

4 系統仿真

本節采用MATLAB對協議進行仿真。選擇分簇個數、匯點路徑長度(跳數)和網絡壽命3個指標評估算法性能。將本協議記為EEMS，與同樣引入移動匯點的TRACK協議進行比較。實驗場景為節點隨機分布在100 m×100 m的正方形區域內，節點數N取50～400。實驗仿真結果如圖2～圖4所示。

圖2 不同節點密度和通信半徑下分簇個數對比

圖2給出了在不同的網絡節點密度和分簇半徑R情況下，采用分布式分簇算法得到的簇個數，可以看出簇的個數隨著節點密度的增大稍有增加，顯示了網絡的可擴展性良好;另一方面，在不同的通信半徑下簇的規模相應增加，表明分簇半徑越小獲得的簇個數越多，骨干網節點數目也就越多。

圖3 通信半徑固定(R=20 m)分簇個數與路長關系

圖3給出了移動匯點MS路徑長度、跳數和簇個數之間的關系，同時給出了TRACK協議在相同的骨干節點數目情況下的路長，通過對比可以看出本協議獲得的路長和跳數都明顯變短。將網絡壽命定義為網絡開始工作到網絡中第一個節點耗光能量的時間段。統一通信半徑為20 m，以LEACH協議在50個節點情況下的網絡壽命為基準1，圖4給出了本協議、LEACH協議和TRACK協議網絡壽命對比關系，從圖中可以看出隨著節點數目的增多網絡壽命都呈現了一定的增長。采用移動匯點機制的TRACK協議和EEMS協議相對LEACH協議網絡壽命具有顯著增長，驗證了移動匯點的引入對網絡壽命具有非常顯著的改善作用。同TRACK協議相比EEMS通過使用更加高效的MST生成算法、構建更短的匯點移動軌跡等機制使得傳感器網絡壽命有了進一步的提升。

圖4 通信半徑固定(R=20 m)節點密度與網絡壽命的關系

5 結束語

綜合利用分簇、移動匯點技術，提出一種能量高效的無線傳感器網絡數據收集協議。通過分布式分簇機制生成網絡通信的骨干網，有利于大規模無線網絡的可擴展性和穩定性。對骨干網節點采用一種適合資源受限的無線網絡的分布式MST算法生成骨干網節點的最小生成樹，并在此基礎上借助解決TSP問題的思想構建移動匯點的移動軌跡。在該移動軌跡上MS和每個簇以單跳方式通信，有效避免了信道競爭和沖突，提高了通信質量，緩解了熱點問題的發生。

［1］ Lian J，Naik K，Agnew G.Data Capacity Improvement of Wireless Sensor Networks Using Non-Uniform Sensor Distribution［J］.Int’l J.Distributed Sensor Networks，2006，2(2):121－145.

［2］ Ammari H M，Das S K.Promoting Heterogeneity，Mobility and Energy-Aware Voronoi Diagram in Wireless Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(7):995－1008.

［3］ Zhang H，Shen H.Balancing Energy Consumption to Maximize Network Lifetime in Data-Gathering Sensor Networks［J］.IEEE Transactions on Parallel and Distributed Systems，2009，20(10):1526－1539.

［4］ Chen G，Li C F，Ye M，et al.An Unequal Cluster-Based Routing Strategy in Wireless Sensor Networks［J］.Wireless Networks，2009，15(2):193－207.

［5］ 章搖韻，宋汝蕓，陳搖志，等.基于簇頭選擇的移動傳感網拓撲控制算法研究［J］.傳感技術學報，2011，24(11):1602－1606.

［6］ Di Francesco M，Das S K，Anastasi G.Data Collection in Wireless Sensor Networks with Mobile Elements:A Survey［J］.ACM Transactions on Sensor Networks，2011，8(1):1－34.

［7］ Basagni S，Carosi A，Melachrinoudis E，et al.Controlled Sink Mobility for Prolonging Wireless Sensor Networks Lifetime［J］.ACM Wireless Networks，2008，14(6):831－858.

［8］ Wang W，Srinivasan V，Chua K C.Using Mobile Relays to Prolong the Lifetime of Wireless Sensor Networks［C］//Proc.of ACM MobiCom，2005:270－283.

［9］ Luo J，Hubaux J P.Joint Mobility and Routing for Lifetime Elongation in Wireless Sensor Networks［C］//Proc.of IEEE Infocom，vol.3，2005:1735－1746.

［10］ Nesamony S，Vairamuthu M K，Orlowska M E.On Optimal Route of a Calibrating Mobile Sink in a Wireless Sensor Network［C］//Proc.of the 4th International Conference on Networked Sensing Systems(INSS)，2007:61－64.

［11］ Rao J，Biswas S.Joint Routing and Navigation Protocols for Data Harvesting in Sensor Networks［C］//Proc.of the 5th IEEE International Conference on Mobile Ad Hoc and Sensor Systems(MASS)，2008:143－152.

［12］ Rao J，Biswas S.Network Assisted Sink Navigation for Distributed Data Gathering:Stability and Delay-Energy Trade-Offs［J］.Computer Communications，2010，33(2):160－175.

［13］ Srinivasan AWu J.TRACK:A Novel Connected Dominating Set based Sink Mobility Model for WSNs［C］//Proc.ICCCN 2008:664－671.

［14］ Gallager R G，Humblet P A，Spira P M.A Distributed Algorithm for Minimum-Weight Spanning Trees［J］.ACM Transactions on Programming Languages and Systems，1983，5(1):66－77.

［15］ Mhatre V，Rosenberg C.Design Guidelines for Wireless Sensor Networks Communication:Clustering and Aggregation［J］.Ad-Hoc Networks Journal，2004，2(1):45－63.

［16］ Khan M，Pandurangan G，Anil Kumar V S.Distributed Algorithms for Constructing Approximate Minimum Spanning Trees in Wireless Sensor Networks［J］.IEEE Transations on Parallel and Distributed Systems，2009，20(1):124－139.