無線傳感器網絡中節點部署算法研究綜述*

郭秀明，周國民，樊景超

(中國農業科學院 農業信息研究所，北京100081)

0 引 言

無線傳感器網絡(WSNs)是由大量傳感器節點通過無線通信技術形成的多跳網絡。憑借其分布式處理帶來的監測精度高、容錯性能好、覆蓋區域大、可遠程監控等優點，WSNs 已成為國內外研究的熱點［1］。

節點部署和覆蓋控制是WSNs 應用中的一個基本問題，它在一定程度上決定了網絡感知質量、網絡應用成本及使用的能耗［2］。在保證一定的服務質量條件下，如何達到網絡覆蓋范圍最大化，提供可靠的監測和目標跟蹤服務，網絡覆蓋是否存在監測和通信盲區，是否需要重新調整傳感器節點分布以完成目標監測和信息獲取的任務都是WSNs部署所包含的問題。節點部署具體主要解決以下三個問題:1)節點的種類和數目;2) 節點的部署方式;3) 網絡的可靠性與自適應性。

已有眾多的研究者提出了很多WSNs 部署方法。本文比較分析目前節點部署方法，分別從部署方式、監測目標、網絡架構及節點是否移動等多個角度分析節點部署方法的應用現狀。最后，給出了WSNs 部署算法的應用關鍵點與未來發展趨勢。

1 從部署方式上劃分

WSNs 的節點部署方式隨著應用場景的不同可劃分為隨機部署和手工部署。在一些環境惡劣的人類很難進入的環境，如，戰場、原始森林等，須通過飛機將節點散播到目標區域，節點通過自組網監測信息。但在人類友好的環境，如工廠車間、農田等，人類方便出入和控制，手工部署能精確地放置節點的位置，根據預先的規劃部署使用最少的節點實現感興趣信息的采集，節省成本，延長網絡生存周期。

隨機部署方式通過飛機拋灑大量的節點到目標區域。高密度的節點組成的網絡存在很大的冗余性，目前較多的方法是將節點分組，每一組節點交替輪回的醒來工作，其他組的節點睡眠以節省能量并延長網絡生命周期［3～5］。

在農田、工廠等環境，人類出入方便，手工部署能根據監測需求預先設定信息采集和傳輸方案，及時解決發現的問題，方便更換電源。Shen X 等人［6］在已有部分部署節點的情況下，提出了一種基于網格掃描的再部署方法，能使用最少的節點實現對要求區域的k覆蓋。楊明華［7］針對未知環境下移動傳感器網絡的部署問題，提出了一種基于虛擬力的精確部署算法。劉卉等人［8］設計了等邊三角形、正方形、正六邊形規則網格的系統節點部署和系統隨機節點部署兩種方法，并分別給出了兩種方法中三種規則網格單元邊長最大值的求解方法。李明［9］針對異構傳感器網絡節點的高密度部署和監測目標非均勻分布的情況，提出了一種基于模擬退火算法的成本最優部署方法。

2 從節點是否移動劃分

從節點的位置在網絡應用過程中是否變化上劃分可以分為靜態部署和動態部署。節點的靜態部署方案先于網絡啟動，部署方案獨立于網絡的狀態并且貫穿于整個網絡生命周期。靜態部署的大部分協議往往只在初始化時計算一次節點的位置，并沒有考慮到節點一旦被定位后發生移動和網絡運行的動態變化的情況。張輪［10］通過引入粒子群優化方法，在即有的隨機布設的WSNs 中，尋找最佳匯聚節點位置。溫俊［11］從提高能量效率和降低剩余能量的角度提出了節點數遞減的重疊放置方法和節點密度遞減的隨機部署方法。

網絡狀態在一些情況下是變化的，應用層對網絡造成的影響也會隨時間而變化。當新節點的加入或節點耗盡能量時，可利用的網絡資源與網絡拓撲會發生變化。動態部署能進一步提高網絡性能。與首次部署不同的是，這種重新部署是為了適應變化的網絡或基于環境的刺激。動態部署需要周期性地檢測網絡狀態和性能以及分析在節點周圍可能發生的事情。戶曉玲［12］提出了一種新的基于微粒群模型的移動傳感器節點位置優化配置算法，建立節點部署優化模型，利用微粒群算法求解該優化模型，優化過程中的最優解作為節點的最終配置位置。Wang Y C［13］考慮了網絡啟動前使用最少靜態節點的放置問題和網絡啟動后移動節點的移動布局策略問題，對于后者提出了基于競爭和基于模型兩種方法。Senturk I F 等人［14］針對中繼節點在非連通的WSNs 中擔任信息轉發和信息采集角色的數目問題提出了一種中繼節點的部署方法，既保證網絡連通性，又平衡承擔信息轉發和信息采集的中繼節點的個數，以最小化信息鏈長度，并滿足一種強加的覆蓋要求。

3 按網絡架構劃分

從網絡架構上劃分，部署方法可以分為同構部署和異構部署。同構網絡中，所有的節點都具有采集、存儲、路由、及信息傳輸的功能，且具有相同的感知距離和通信距離，如圖1(a)所示。WSNs 在應用中不僅僅要求能采集到感興趣的信息，同時節點又必須是連通的，以便采集的信息能傳輸回匯聚節點。所以，WSNs 部署既要考慮到信息的覆蓋和感知，又要考慮到網絡連通問題。Zhang H 等人［15］證實，若節點的傳輸距離大于或等于節點覆蓋距離的2 倍，則只要網絡是全覆蓋的，則網絡就是連通的。Bai X 等人［16］提出了一組優化的WSNs 節點部署模型，尤其考慮了節點覆蓋距離遠小于節點通信距離的情況下。蔣麗萍等人［17］提出了一種分布式k 重覆蓋算法，算法采用了感知概率模型，依據節點感知能力的強弱，根據能量大小競選找出k 組不相交工作節點集，保證監測區域中每一點被k 重覆蓋。

為了延長網絡生命周期或者最小化傳輸延遲，一些部署設計為節點定義了不同的角色。如圖1(b)所示。權建國等人［18］將節點劃分為兩類:負責信息感知功能的普通節點和具有較長通信距離負責傳輸數據的超級節點。Wang C F 等人［19］針對移動匯聚節點的定位問題，提出了一種能量感知的匯聚節點重定位算法，根據感知節點的剩余能量自動調整節點的傳輸距離和匯聚節點的重定位策略。

圖1 同構網絡和異構網絡示意圖Fig 1 Diagram of an isomorphic WSNs and a heterogeneous WSNs

4 從監測目標劃分

從監測對象劃分，主要可劃分為區域監測、目標監測、邊緣監測等。區域覆蓋的目的是使所監測的區域內所有的點都至少被一個傳感器節點覆蓋，即整個區域面積都要被感知，如圖2(a)所示。He X 等人［20］針對在高密度的節點如何從中選取其子集以實現對整個區域覆蓋的問題提出了一種節點劃分的方法，并給出了所能劃分的最大集合數目的方法，Santpal S D［21］提出了兩種有效的傳感器節點放置方法，旨在使用最少的傳感器實現區域覆蓋并能給出節點的放置位置。

目標監測實現對若干離散的目標點的監測［22，23］，如圖2(b)所示。郭秀明等人［24］提出了一種基于網格掃描的實現目標點覆蓋的確定性節點部署算法，同時引入了概率感知模型，把節點能感知到目標點的最小感知概率值作為整體覆蓋水平的評價指標。

邊界監測和跟蹤是指監測和追蹤某一事件的邊緣和運動趨勢(圖2(c))。Subhasri D 等人［25］提出了一種動態邊界跟蹤算法，融合了空間估算和時間估算技術，和定期更新信息方法來跟蹤邊界的方法相比，本文所提方法無需動態邊界的先前知識且節省能量。Hung K S［26］提出了一種分布式的算法尋找最小的覆蓋集以實現對邊界的覆蓋和監測。通過仿真實驗證實了算法的優越性。

區域監測、目標點監測、邊界監測是WSNs 應用中常見的三種監測目標，WSNs 會針對實際需求實現不同的監測功能，如，事件監測［27］、三維空間的監測［28］、面積較大的目標的部分監測［29］等。

圖2 三種不同的監測對象Fig 2 Three different monitoring objects

5 結束語

本文分析目前WSNs 節點部署方法研究現狀，并分別從部署方式、監測目標、網絡架構及節點是否移動等多個角度對目前的研究現狀進行歸納總結。節點部署是WSNs 應用中的技術，決定了WSNs 應用的性能。不同的應用需求決定不同的WSNs 應用部署方案。合理正確的部署是WSNs 可靠高效運行的基礎，但還需要合適的通信協議配合。節點的部署方案和通信協議是相互影響和制約的，只有好的部署方案而缺乏適宜的通信協議，WSNs 仍不能有效運行。目前已有眾多研究者分別關注部署策略和WSNs 通信協議的研究，而關于兩者之間的關系的研究尚不多見。針對特定的應用場景和需求，研究適宜的節點部署方案及其相應的傳輸協議為WSNs 的標準化應用打下基礎。

［1］ Esch J.A survey on topology control in wireless sensor networks:Taxonomy，comparative study，and open issues［C］∥Proceedings of the IEEE，2013:2534－2537.

［2］ 朱海洋，張 合，馬少杰，等.無線傳感器網絡覆蓋質量遠程監控系統［J］.傳感器與微系統，2014，33(12):107－109.

［3］ Tian D，Georganas N D.A coverage－preserving node scheduling scheme for large wireless sensor networks［C］∥Proceedings of the ACM International Workshop on Wireless Sensor Networks and Applications，2002:32－41.

［4］ Gupta H，Zhou Z，Das S R，et al.Connected sensor cover:Self－organization of sensor networks for efficient query execution［J］.IEEE/ACM Transactions on Networking，2006，14(1):55－67.

［5］ 蔣 杰，方 力，張鶴穎，等.無線傳感器網絡最小連通覆蓋集問題求解算法［J］.軟件學報，2006，17(2):175－184.

［6］ Shen X，Chen J，Sun Y.Grid scan:A simple and effective approach for coverage issue in wireless sensor networks［C］∥IEEE Proceedings of the ICC，2006:480－484.

［7］ 楊明華，曹元大，譚 勵，等.一種移動傳感器網絡精確部署算法［J］.北京理工大學學報，2009，29(1):27－31.

［8］ 劉 卉，孟志軍，徐 敏，等.基于規則網格的農田環境監測傳感器節點部署方法［J］.農業工程學報，2011，27(8):265－270.

［9］ 李 明，石為人.異構無線傳感器網絡中基于模擬退火算法的成本最優部署機制［J］.傳感技術學報，2010，23(6):855－858.

［10］張 輪，陸 琰，董德存，等.一種無線傳感器網絡覆蓋的粒子群優化方法［J］.同濟大學學報:自然科學版，2009，37(2):262－266.

［11］溫 俊，竇 強，蔣 杰，等.無線傳感器網絡中保證覆蓋的最少節點部署［J］.國防科技大學學報，2009，31(3):76－81.

［12］戶曉玲，曾建潮.基于微粒群模型的移動傳感器網絡部署研究［J］.計算機技術與發展，2009，19(10):81－88.

［13］Wang Y C，Tseng Y C.Distributed deployment schemes for mobile wireless sensor networks to ensure multilevel coverage［J］.IEEE Transactions on Parallel and Distributed Systems，2008，19(9):1280－1294.

［14］Senturk I F，Akkaya K.Energy and coverage trade－offs in deploying a mix of mobile and stationary relays for disjoint wireless sensor networks［C］∥2013 IEEE Global Communications Conference(GLOBECOM)，2013:249－254.

［15］Zhang H，Hou J C.Maintaining sensing coverage and connectivity in large sensor networks［J］.Ad Hoc Wireless Sensor Networks，2005(1):89－124.

［16］Bai X，Yun Z，Xuan D，et al.Pattern mutation in wireless sensor deployment［C］∥IEEE Proceedings INFOCOM，2010:1－9.

［17］蔣麗萍，王良民，熊書明，等.基于感知概率的無線傳感器網絡k 重覆蓋算法［J］.計算機應用研究，2009，26(9):3484－3489.

［18］權建國，王國軍，邢蕭飛.無線傳感器網絡中基于異構節點的覆蓋控制算法［J］.傳感技術學報，2010，23(6):863－867.

［19］Wang C F，Shih J D，Pan B H，et al.A network lifetime enhancement method for sink relocation and its analysis in wireless sensor networks［J］.IEEE Sensors Journal，2014，14(6):1932 －1943.

［20］He X，Yang H，Gui X.The maximum coverage set calculated algorithm for WSNs area coverage［J］.Journal of Networks，2010，5(6):650－657.

［21］Santpal S D，Krishnendu C.Sensor pacement for effective coverage and surveillance in distributed sensor networks［C］∥Proceedings of IEEE Wireless Communications and Networking Conference，2003:1609－1614.

［22］Mohammad A J，Navid B，Mohammad E，et al.An energy－efficient algorithm for connected target coverage problem in wireless sensor networks［C］∥IEEE International Conference on Computer Science and Information Technology(ICCSIT)，2010:249－254.

［23］何 欣，桂小林，安 健.面向目標覆蓋的無線傳感器網絡確定性部署方法［J］.西安交通大學學報，2010，44(6):6－15.

［24］郭秀明，趙春江，楊信廷，等.基于網格掃描的實現目標點覆蓋的確定性傳感器節點部署方法［J］.傳感技術學報，2012，25(1):104－109.

［25］Subhasri D，Krithi R.Tracking dynamic boundaries using sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22(10):1766－1774.

［26］Hung K S，Lui K S.On perimeter coverage in wireless sensor networks［J］.IEEE Transactions on Wireless Communications，2010，9(7):2156－2164.

［27］石為人，楊 斌，許 磊，等.一種事件驅動型無線傳感器網絡目標追蹤算法的研究［J］.傳感技術學報，2010，23(1):144－148.

［28］Zhang C，Bai X，Teng J，et al.Constructing low－connectivity and full－coverage three dimensional sensor networks［J］.IEEE Journal on Selected Areas in Communications，2010，28(7):984－992.

［29］Li Y，Vu C，Ai C，et al.Transforming complete coverage algorithms to partial coverage algorithms for wireless sensor networks［J］.IEEE Transactions on Parallel and Distributed Systems，2011，22(4):695－702.