郭秀明，周國民，樊景超

(中國農(nóng)業(yè)科學(xué)院 農(nóng)業(yè)信息研究所，北京100081)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)是由大量傳感器節(jié)點(diǎn)通過無線通信技術(shù)形成的多跳網(wǎng)絡(luò)。憑借其分布式處理帶來的監(jiān)測精度高、容錯(cuò)性能好、覆蓋區(qū)域大、可遠(yuǎn)程監(jiān)控等優(yōu)點(diǎn)，WSNs 已成為國內(nèi)外研究的熱點(diǎn)［1］。

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

已有眾多的研究者提出了很多WSNs 部署方法。本文比較分析目前節(jié)點(diǎn)部署方法，分別從部署方式、監(jiān)測目標(biāo)、網(wǎng)絡(luò)架構(gòu)及節(jié)點(diǎn)是否移動(dòng)等多個(gè)角度分析節(jié)點(diǎn)部署方法的應(yīng)用現(xiàn)狀。最后，給出了WSNs 部署算法的應(yīng)用關(guān)鍵點(diǎn)與未來發(fā)展趨勢。

1 從部署方式上劃分

WSNs 的節(jié)點(diǎn)部署方式隨著應(yīng)用場景的不同可劃分為隨機(jī)部署和手工部署。在一些環(huán)境惡劣的人類很難進(jìn)入的環(huán)境，如，戰(zhàn)場、原始森林等，須通過飛機(jī)將節(jié)點(diǎn)散播到目標(biāo)區(qū)域，節(jié)點(diǎn)通過自組網(wǎng)監(jiān)測信息。但在人類友好的環(huán)境，如工廠車間、農(nóng)田等，人類方便出入和控制，手工部署能精確地放置節(jié)點(diǎn)的位置，根據(jù)預(yù)先的規(guī)劃部署使用最少的節(jié)點(diǎn)實(shí)現(xiàn)感興趣信息的采集，節(jié)省成本，延長網(wǎng)絡(luò)生存周期。

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

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

2 從節(jié)點(diǎn)是否移動(dòng)劃分

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

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

3 按網(wǎng)絡(luò)架構(gòu)劃分

從網(wǎng)絡(luò)架構(gòu)上劃分，部署方法可以分為同構(gòu)部署和異構(gòu)部署。同構(gòu)網(wǎng)絡(luò)中，所有的節(jié)點(diǎn)都具有采集、存儲(chǔ)、路由、及信息傳輸?shù)墓δ埽揖哂邢嗤母兄嚯x和通信距離，如圖1(a)所示。WSNs 在應(yīng)用中不僅僅要求能采集到感興趣的信息，同時(shí)節(jié)點(diǎn)又必須是連通的，以便采集的信息能傳輸回匯聚節(jié)點(diǎn)。所以，WSNs 部署既要考慮到信息的覆蓋和感知，又要考慮到網(wǎng)絡(luò)連通問題。Zhang H 等人［15］證實(shí)，若節(jié)點(diǎn)的傳輸距離大于或等于節(jié)點(diǎn)覆蓋距離的2 倍，則只要網(wǎng)絡(luò)是全覆蓋的，則網(wǎng)絡(luò)就是連通的。Bai X 等人［16］提出了一組優(yōu)化的WSNs 節(jié)點(diǎn)部署模型，尤其考慮了節(jié)點(diǎn)覆蓋距離遠(yuǎn)小于節(jié)點(diǎn)通信距離的情況下。蔣麗萍等人［17］提出了一種分布式k 重覆蓋算法，算法采用了感知概率模型，依據(jù)節(jié)點(diǎn)感知能力的強(qiáng)弱，根據(jù)能量大小競選找出k 組不相交工作節(jié)點(diǎn)集，保證監(jiān)測區(qū)域中每一點(diǎn)被k 重覆蓋。

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

圖1 同構(gòu)網(wǎng)絡(luò)和異構(gòu)網(wǎng)絡(luò)示意圖Fig 1 Diagram of an isomorphic WSNs and a heterogeneous WSNs

4 從監(jiān)測目標(biāo)劃分

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

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

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

區(qū)域監(jiān)測、目標(biāo)點(diǎn)監(jiān)測、邊界監(jiān)測是WSNs 應(yīng)用中常見的三種監(jiān)測目標(biāo)，WSNs 會(huì)針對實(shí)際需求實(shí)現(xiàn)不同的監(jiān)測功能，如，事件監(jiān)測［27］、三維空間的監(jiān)測［28］、面積較大的目標(biāo)的部分監(jiān)測［29］等。

圖2 三種不同的監(jiān)測對象Fig 2 Three different monitoring objects

5 結(jié)束語

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

［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］ 朱海洋，張 合，馬少杰，等.無線傳感器網(wǎng)絡(luò)覆蓋質(zhì)量遠(yuǎn)程監(jiān)控系統(tǒng)［J］.傳感器與微系統(tǒng)，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］ 蔣 杰，方 力，張鶴穎，等.無線傳感器網(wǎng)絡(luò)最小連通覆蓋集問題求解算法［J］.軟件學(xué)報(bào)，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］ 楊明華，曹元大，譚 勵(lì)，等.一種移動(dòng)傳感器網(wǎng)絡(luò)精確部署算法［J］.北京理工大學(xué)學(xué)報(bào)，2009，29(1):27－31.

［8］ 劉 卉，孟志軍，徐 敏，等.基于規(guī)則網(wǎng)格的農(nóng)田環(huán)境監(jiān)測傳感器節(jié)點(diǎn)部署方法［J］.農(nóng)業(yè)工程學(xué)報(bào)，2011，27(8):265－270.

［9］ 李 明，石為人.異構(gòu)無線傳感器網(wǎng)絡(luò)中基于模擬退火算法的成本最優(yōu)部署機(jī)制［J］.傳感技術(shù)學(xué)報(bào)，2010，23(6):855－858.

［10］張 輪，陸 琰，董德存，等.一種無線傳感器網(wǎng)絡(luò)覆蓋的粒子群優(yōu)化方法［J］.同濟(jì)大學(xué)學(xué)報(bào):自然科學(xué)版，2009，37(2):262－266.

［11］溫 俊，竇 強(qiáng)，蔣 杰，等.無線傳感器網(wǎng)絡(luò)中保證覆蓋的最少節(jié)點(diǎn)部署［J］.國防科技大學(xué)學(xué)報(bào)，2009，31(3):76－81.

［12］戶曉玲，曾建潮.基于微粒群模型的移動(dòng)傳感器網(wǎng)絡(luò)部署研究［J］.計(jì)算機(jī)技術(shù)與發(fā)展，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］蔣麗萍，王良民，熊書明，等.基于感知概率的無線傳感器網(wǎng)絡(luò)k 重覆蓋算法［J］.計(jì)算機(jī)應(yīng)用研究，2009，26(9):3484－3489.

［18］權(quán)建國，王國軍，邢蕭飛.無線傳感器網(wǎng)絡(luò)中基于異構(gòu)節(jié)點(diǎn)的覆蓋控制算法［J］.傳感技術(shù)學(xué)報(bào)，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］何 欣，桂小林，安 健.面向目標(biāo)覆蓋的無線傳感器網(wǎng)絡(luò)確定性部署方法［J］.西安交通大學(xué)學(xué)報(bào)，2010，44(6):6－15.

［24］郭秀明，趙春江，楊信廷，等.基于網(wǎng)格掃描的實(shí)現(xiàn)目標(biāo)點(diǎn)覆蓋的確定性傳感器節(jié)點(diǎn)部署方法［J］.傳感技術(shù)學(xué)報(bào)，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］石為人，楊 斌，許 磊，等.一種事件驅(qū)動(dòng)型無線傳感器網(wǎng)絡(luò)目標(biāo)追蹤算法的研究［J］.傳感技術(shù)學(xué)報(bào)，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.