凡高娟，郭拯危

(1.河南大學計算機與信息工程學院，河南開封475004;2.南京大學江蘇省無線傳感網(wǎng)高技術研究重點實驗室，江蘇南京210003)

0 引言

傳感器網(wǎng)絡節(jié)點部署是實現(xiàn)網(wǎng)絡應用的一個基本問題［1］，目的是采用感知受限和能量約束的傳感器網(wǎng)絡建立一個功能強大的系統(tǒng)。在節(jié)點部署中，覆蓋、連通性、部署代價、生存時間將對網(wǎng)絡的有效性和實用性等起決定性作用。另外，傳感器節(jié)點處理能力和資源都受限。設計者面臨建立高可靠性和長持續(xù)性的應用需求與資源受限設備的挑戰(zhàn)，所以，必須通過有效的節(jié)點部署機制。

根據(jù)應用需求和部署條件來選擇采用何種部署方案［2］。如傳感器通常工作在惡劣環(huán)境或人類不能到達的區(qū)域，節(jié)點往往采用隨機部署。此時，節(jié)點的數(shù)目、感知半徑和網(wǎng)絡的覆蓋率之間的某種函數(shù)關系，在初期部署時，根據(jù)這種函數(shù)關系計算所需節(jié)點的數(shù)目和調(diào)節(jié)節(jié)點的感知范圍和通信范圍［3］。

目前在傳感器節(jié)點部署方面進行了很多研究，節(jié)點的部署與網(wǎng)絡覆蓋、連通和能耗等研究相關。本文從靜態(tài)部署和動態(tài)部署2個方面介紹當前節(jié)點部署的研究現(xiàn)狀。

1 靜態(tài)部署

靜態(tài)部署是根據(jù)最優(yōu)的策略來決定節(jié)點的位置，節(jié)點放置通常在網(wǎng)絡啟動之前，并且節(jié)點的位置在整個網(wǎng)絡生存期間不變。依據(jù)部署方法、優(yōu)化對像和節(jié)點的角色，對目前存在的靜態(tài)部署方法進行歸類，如圖1所示。

1.1 部署方法

無線傳感器網(wǎng)絡的部署方法與應用密切相關，根據(jù)應用環(huán)境的不同，無線傳感器網(wǎng)絡的部署方法可以分為兩類:確定性部署和隨機部署兩類［4］。

圖1 節(jié)點靜態(tài)部署分類Fig 1 Classification of node’s static deployment

確定性部署通常應用于網(wǎng)絡的狀態(tài)相對固定或應用環(huán)境、節(jié)點位置信息、節(jié)點的密度等已知情況下。確定性部署通過對問題進行數(shù)學抽象，成為靜態(tài)優(yōu)化問題或線性規(guī)劃問題，如在文獻［5］中，得出節(jié)點部署達到覆蓋所需要的最少節(jié)點個數(shù)和給出節(jié)點相應的位置。在文獻［6］中，利用六形網(wǎng)格來部署節(jié)點，達到最大的連通覆蓋。確定性部署方法簡單，但在實際的應用中，尤其是大規(guī)模、無人監(jiān)守的惡劣環(huán)境中，隨機部署顯得更具有優(yōu)勢。當監(jiān)測區(qū)域環(huán)境惡劣或存在危險時，隨機部署是唯一的選擇。此時，通過飛機、炮彈等載體把節(jié)點隨機拋撒在監(jiān)測區(qū)域內(nèi)，節(jié)點到達地面以后自組成網(wǎng)。這種隨機性主要體現(xiàn)在2個方面:一是節(jié)點落在監(jiān)測區(qū)域內(nèi)的位置具有隨機性;二是受環(huán)境的影響，落在區(qū)域內(nèi)的節(jié)點狀態(tài)具有一定的隨機性，某些節(jié)點可能會在墜落過程中損壞而失效。因而，在隨機部署策略下，為取得較好的覆蓋性能，必須投入大量的冗余節(jié)點以達到所需要的節(jié)點密度。隨機部署方式是一種較為經(jīng)濟適用的方法，但不能保證整個監(jiān)測區(qū)域完全覆蓋，一般適用于對覆蓋要求不太嚴格的應用環(huán)境中。文獻［7］分析了漸近性分析方法在實際部署中帶來的問題。

在確定性部署與隨機部署的選擇上，文獻［8］指出，在進行節(jié)點部署時，分析需要用多少個節(jié)點來達到一定的覆蓋度，維護k覆蓋所需要的節(jié)點個數(shù)依賴于監(jiān)測區(qū)域的面積和部署策略，作者分析了達到k覆蓋在泊松到達部署、均勻部署和格部署3種部署策略下所需要的節(jié)點密度，得出格部署在大多數(shù)情況下比隨機部署需要更少的節(jié)點。

1.2 優(yōu)化對象

根據(jù)優(yōu)化對象對部署進行分類，可以分為基于覆蓋、基于網(wǎng)絡連通和能量有效性部署三類。

最大化監(jiān)測區(qū)域的覆蓋受到越來越多研究者的重視。文獻［9］提出故障容錯的k連通部署方案，分析用最少的額外節(jié)點使網(wǎng)絡為k連通;并對于給定的k，可以求得部署的節(jié)點個數(shù)，用貪婪和分布式方法實現(xiàn)該算法。

文獻［10］通過2種基本的部署方法:Square-grid和Hex-grid 2種方法，提出一種自低向上的方法評價網(wǎng)絡的生存時間，把單個節(jié)點的生存時間和網(wǎng)絡的生存時間作為隨機變量來模擬，推導概率密度函數(shù)。文獻［11］分析高斯部署下節(jié)點的覆蓋與生存時間之間的關系，但沒有考慮部署中存在的邊界問題。

1.3 節(jié)點角色

節(jié)點的部署位置不僅影響節(jié)點的覆蓋與連通，更影響網(wǎng)絡的生存時間。一些學者利用不同類型的節(jié)點來優(yōu)化網(wǎng)絡性能(增加網(wǎng)絡生存時間、最小化數(shù)據(jù)包延遲等)。節(jié)點在網(wǎng)絡中可以充當感知節(jié)點、中間節(jié)點、基站節(jié)點或簇頭節(jié)點。當節(jié)點充當不同的角色時，網(wǎng)絡的性能參數(shù)依賴于節(jié)點在網(wǎng)絡中的角色。文獻［12］通過在室內(nèi)部署中間節(jié)點達到網(wǎng)絡的連通性與網(wǎng)絡生存時間延長的目的。

2 動態(tài)部署

節(jié)點動態(tài)部署可以追溯到機器人的部署，國內(nèi)外已有研究機構進行了相關研究，基于動態(tài)部署的方式可以分為如下3種，如圖2所示。

圖2 動態(tài)部署分類Fig 2 Classification of dynamic deployment

2.1 增量式節(jié)點部署算法

文獻［13］提出一種增量式節(jié)點部署方法，通過逐個部署節(jié)點，利用已經(jīng)部署的節(jié)點計算出下一個節(jié)點應該部署的位置，達到網(wǎng)絡的覆蓋面積最大。該算法需要每個節(jié)點都有測距和定位模塊，適用于監(jiān)測區(qū)域環(huán)境未知的情況。優(yōu)點是利用最少的節(jié)點覆蓋監(jiān)測區(qū)域;缺點是部署時間長，部署每一個節(jié)點可能需要移動多個節(jié)點。

2.2 基于人工勢場(或虛擬力)的算法

該類算法把人工勢場(或虛擬力)用于移動節(jié)點的自展開問題，把網(wǎng)絡中的每個節(jié)點作為一個虛擬的正電荷，每個節(jié)點受到邊界障礙和其他節(jié)點的排斥，這種排斥力使整個網(wǎng)絡中的所有節(jié)點向感知網(wǎng)中的其他地域擴散，并避免越出邊界，最終達到平衡狀態(tài)，即達到感知區(qū)域的最大覆蓋狀態(tài)。

Zou Y等人提出VFA算法［14］基本思想是假設部署區(qū)域中存在3種力:一是障礙物對節(jié)點的斥力，二是對覆蓋率要求高的區(qū)域產(chǎn)生的引力，三是節(jié)點之間產(chǎn)生的引力或斥力。算法計算產(chǎn)生在每個節(jié)點上的合力來控制節(jié)點之間的距離與節(jié)點移動，缺點是沒有為可能出現(xiàn)的節(jié)點碰撞提供解決方案。優(yōu)點是算法簡單易用，并能達到節(jié)點快速擴散到整個感知區(qū)域的目的，同時每個節(jié)點所移動的路徑比較短。

2.3 利用節(jié)點間的移動

文獻［15］通過利用部分節(jié)點的有限移動，完成覆蓋空洞，達到網(wǎng)絡k覆蓋的目的。

3 節(jié)點部署方法比較

下面對目前常見的無線傳感器網(wǎng)絡部署方法進行比較，其結果見表1。

表1 節(jié)點部署方法比較Tab 1 Comparison of node deployment methods

通過表1，可以從整體上清晰認識各種部署策略。此外，對相關研究成果的優(yōu)缺點比較，有助于更加全面的了解已有的部署策略，并進一步發(fā)現(xiàn)和考慮一些凾待解決的問題。

4 節(jié)點部署中存在的問題

針對以上文獻進行分析，節(jié)點部署中存在的問題可以歸為以下幾點:

1)部署誤差不可忽視:目前研究假設節(jié)點部署不存在部署誤差，在部署誤差存在的情況下，如何建立有效的模型，在節(jié)點感知半徑、監(jiān)測區(qū)域面積已知的情況下，確定最佳的部署節(jié)點個數(shù)。

2)忽略邊界因素影響:沒有考慮到監(jiān)測區(qū)域邊界對于網(wǎng)絡的覆蓋與連通帶來的影響［16］，通常采用漸近性分析方法，基于這些假設的分析結果在實際部署應用中不能達到所需要的覆蓋性能。

3)感知和通信模型過于理想:假設傳感器節(jié)點的感知模型和通信模型是理想的圓盤模型，不能適用于實際環(huán)境的感知模型多樣化需要。

4)容錯部署問題:當網(wǎng)絡中某些節(jié)點能量耗盡或者發(fā)生故障時，可能出現(xiàn)覆蓋“空洞”，使得網(wǎng)絡出現(xiàn)分割，甚至導致網(wǎng)絡的不連通，需要重新對網(wǎng)絡進行部署。

5)部署空間擴展問題:大多數(shù)無線傳感器網(wǎng)絡應用是在三維空間中。如何針對具體的WSNs三維空間應用需要設計出有效的算法與協(xié)議，是一個很有意義的研究課題。

5 結束語

由于無線傳感器網(wǎng)絡資源有限且是應用相關的網(wǎng)絡，研究人員研究多種節(jié)點部署策略來滿足其應用需求和新特性。本文從靜態(tài)和動態(tài)2種部署方式介紹了節(jié)點部署的分類與應用要求，分析各種部署策略的優(yōu)勢及應用環(huán)境。但是，節(jié)點部署作為傳感器應用的一項關鍵技術，還有很多問題需要進一步研究，在滿意應用需求的同時，充分利用其有限資源。

［1］Kenan X.Device deployment strategies for large-scale wireless sensor networks［D］.QSpace at Queen’s University，2008.

［2］Younis O，F(xiàn)ahmy S.HEED:A hybrid，energy-efficient，distributed clustering approach for Ad Hoc sensor networks［J］.IEEE Transactions on Mobile Computing，2004，3(4):366-379.

［3］Mhatre V.A minimum cost heterogeneous sensor network with a lifetime constraint［J］.IEEE Transactions on Mobile Computing，2005，4(1):4-15.

［4］Romer K，Mattern F.The design space of wireless sensor networks［J］.IEEE Wireless Communications，2004，11(6):54-61.

［5］Shakkottai S，Srikant R，Shroff N.Unreliable sensor grids:Coverage，connectivity and diameter［J］.Ad Hoc Networks，2005，3(6):702-716.

［6］Coskun V.Relocating sensor nodes to maximize cumulative connected cove-rage in wireless sensor networks［J］.Sensors，2008，8:2792-2817.

［7］Balister P，Bollobas B，Sarkar A，et al.Reliable density estimates for coverage and connectivity in thin strips of finite length［C］∥The 13th Annual ACM International Conference on Mobile Computing and Networking，Montréal，Québec，Canada，ACM，2007:75-86.

［8］Zhang H，Hou JC.Is deterministic deployment worse than random deployment for wireless sensor networks［C］∥The 25th IEEE International Conference on Computer Communications，Barcelona，Spain，2006:1-13.

［9］Bredin J L，Demaine E D，Hajiaghayi M，et al.Deploying sensor networks with guaranteed capacity and fault tolerance［C］∥The 6th ACM International Symposium on Mobile Ad Hoc Networking and Computing，Urbana-Champaign，IL，USA，ACM，2005:309-319.

［10］Jain E，Qilian L.Sensor placement and lifetime of wireless sensor networks:Theory and performance analysis［C］∥The IEEE Global Telecommunications Conference，2005:5.

［11］Wang D，Xie B，Agrawal D.Coverage and lifetime optimization of wireless sensor networks with Gaussian distribution［J］.IEEE Transactions on Mobile Computing，2008，7(12):1444-1458.

［12］Tarng J，Chuang B，Liu P.A relay node deployment method for disconnected wireless sensor networks:Applied in indoor environments［J］.Journal of Network and Computer Applications，2009，32(3):652-659.

［13］Hu Y，Kang Z，Shen X.An incremental sensor deployment strategy for wireless sensor networks［C］∥1st International Conference on Information Science and Engineering(ICISE)，2009:4721-4724.

［14］Zou Y，Krishnendu C.Sensor deployment and target localization based on virtual forces［C］∥The Twenty-Second IEEE Annual Joint Conference on Computer and Communications，2003:1293-1303.

［15］Yang X，Hui C，Wu Kui，et al.Modeling detection metrics in randomized scheduling algorithm in wireless sensor networks［C］∥The IEEE Wireless Communications and Networking Conference，Kowloon，2007:3741-3745.

［16］Wan PJ，Yi CW.Coverage by randomly deployed wireless sensor networks［J］.IEEE/ACM Trans on Networks，2006，14(S1):2658-2669.