第2章 部署技術的發展和評價指標

2.1 發展現狀

節點部署是在指定的監測區域內，通過適當的方法部署節點以滿足某種特定的需求。節點部署是傳感器網絡進行工作的第一步，它直接關系到網絡監測信息的準確性、完整性和時效性。合理的節點部署不僅可以提高網絡的工作效率，也是無線傳感器網絡研究領域的基本問題之一。目前，關于節點部署的研究中，已經設計出了許多模型和相關算法。這些技術可根據適用環境分為三類：第一類適用于采用確定放置的部署方式；第二類適用于節點不具備移動能力，而且采用隨機拋灑的部署方式；第三類適用于節點具備移動能力，采用隨機拋灑部署方式。

2.1.1 采用確定放置的部署技術

該技術將監測區域劃分為二維或三維網格，并假設傳感器節點分布在網格點上，監測目標也出現于網格點上。假設節點的檢測模型為0/1模型，即如果節點和網格點間距離不大于檢測半徑，則節點能感知該網格點，反之，節點無法感知該網格點。如果每個網格點至少被一個節點所覆蓋，則網絡將覆蓋整個監測區域。每個網格點對應一個監測向量，該向量表示該網格點可以被哪些節點感知。如果不同的網格點對應于不同的監測向量，則可根據監測向量對出現在網格點上的目標進行定位。若某個監測向量對應于多個不同的網格點，則網格點間距越小，定位精度越高，在以上模型的基礎上，可為每個網格點定義一個取值為0或1的整數變量。若以傳感器網絡部署的代價為最小優化目標，以每個網格點都至少被一個節點覆蓋為約束條件，則可以采用商用整數規劃軟件求解。若以網絡定位精度為最高優化目標，以部署代價為約束條件，則可采用模擬退火算法求解。若假設節點的檢測模型為與距離相關的概率檢測模型，即節點對網格點的檢測概率為e-ad，其中，d代表節點與網格點之間的距離，a反映節點的檢測能力。所以d越大，檢測概率越小；a越大，節點對網格點的檢測能力越弱。如果障礙物出現在節點或網格點之間的連線上，則節點對該網格點的檢測概率將降低。另外，每個節點對網格點的檢測相互獨立。如果每個網格點被檢測概率大于指定的閾值，則無線傳感器網絡的感知范圍能覆蓋整個檢測區域。而且，可將較大的閾值設置到具有較高安全可靠程度的網格點，從而對指定區域進行優先覆蓋。在與距離相關的概率檢測模型上，一般使用基于貪婪算法的傳感器網絡部署算法，每次選擇一個網格點并在其放置節點，直到滿足約束條件。

確定性部署通常應用于網絡的狀態相對固定或應用環境已知，節點在網絡中的位置信息以及節點的密度已知情況下。節點的確定性部署通過對問題進行學抽象，可成為靜態優化問題或線性規劃問題[1]。在文獻［2］中，得出節點部署達到覆蓋所需要的最少節點個數并給出了節點相應的位置；在文獻［3］中，利用多邊形網格來部署節點，以實現最大的連通覆蓋。確定性部署能簡化問題的解決方案，但在實際的應用中，尤其是大規模、無人監守的惡劣環境中，隨機部署顯得更具有優勢。

2.1.2 采用隨機拋灑且節點不具移動能力的部署技術

當監測區域環境惡劣或存在危險時，隨機部署是唯一的選擇。同樣，在大規模應用時，由于節點數量眾多、分布密集，采用確定性節點部署技術也不切實際的。此時，可通過飛機、炮彈等載體把節點隨機拋撒在監測區域內，節點到達地面以后自組成網。這種隨機性主要體現在兩個方面[4]：一是節點落在監測區域內的位置具有隨機性；二是由于環境的影響，落在區域內的節點狀態具有一定的隨機性，某些節點可能會在墜落過程中由于損壞而失效。因此，在隨機部署策略下，為取得較好的覆蓋性能，必須投入大量的冗余節點以達到所需要的節點密度。隨機部署方式[5]不能保證部署的節點可以完全覆蓋整個監測區域，一般適用于對覆蓋要求不太嚴格的應用環境中。文獻［6］采用漸近性分析方法分析了在實際隨機部署時帶來的問題。文獻［7］介紹了三種隨機部署模型：簡易擴散模型、均勻模型和R-random模型。

2.1.3 采用隨機拋灑且節點具移動能力的部署技術

針對區域覆蓋的監測應用，基于機器人部署應用中的勢場技術，研究人員提出了采用隨機拋灑，且節點具備移動能力的部署技術。文獻［8］和文獻［9］就通過利用節點的有限移動，完成覆蓋空洞，達到網絡k覆蓋的目的。在傳感器節點向其他節點移動過程中，把移動節點看成虛擬的帶電粒子，假設相鄰節點間0點與障礙物之間存在作用力，每個節點根據受力平衡的原理移動一定距離后，平衡態，這時節點能夠充分覆蓋整個區域。目前，針對該方向已提出一些嵇算法，Zou和Chakrabarty等人提出了VFA算法[10]，其基本思想，一是部署區域中存在障礙物對節點的斥力；二是對覆蓋率要求較高的區域產生的引力；三是節點之間產生的引力或斥力。算法計算產生在每個節點上的合力來控制之間的距離及節點的移動。另一種方法是在部署階段采用拓撲控制技術對節點采取局部分簇策略，每個節點根據周邊節點的能量及分布密度等情況，自適應地調整工作模式，從而提高能量的機用率，若定義節點和被跟蹤目標間存在作用力，則可使節點根據被跟蹤目標的位置和重要性，動態地調整部署，保證在覆蓋區域內提高節點跟蹤能力。李享等人[11]主要研究了在未知覆蓋目標的情況下，如何根據原有的虛擬力算法進行網絡節點的三維部署。作者將虛擬力算法從二維空間拓展到三維空間，創新地提出了自適應中心引力和目標斥力網的概念，使傳感器節點能夠自適應地覆蓋未知目標進行有針對性的探測任務，最終實現了對不同形態的復雜目標進行精確覆蓋。當然，研究人員也提出過一些基于啟發式的算法設計，但這些技術不能有效保證對監測區域的完全覆蓋。李軒涯等人[12]提出了面向空中移動傳感網的帶電粒子群部署模型。作者認為空中移動傳感器網絡應用領域廣闊，動態性強且環境復雜，原有的平面部署策略不再適用，提出的新算法基于帶電粒子群思想，能夠保證監測區域內重點覆蓋與一般覆蓋的均衡。Senel等人[13]討論了水下傳感器網絡中節點的自部署及最大化覆蓋，認為傳感器進入水下環境的困難會使該問題更加復雜化。在文中他們提出了一個完全分布式節點部署方案，同時研究了可能對網絡產生影響的環境因素，如海流、漩渦和隨機表面效應等。