第2章 部署技術(shù)的發(fā)展和評(píng)價(jià)指標(biāo)

2.1 發(fā)展現(xiàn)狀

節(jié)點(diǎn)部署是在指定的監(jiān)測(cè)區(qū)域內(nèi)，通過(guò)適當(dāng)?shù)姆椒ú渴鸸?jié)點(diǎn)以滿足某種特定的需求。節(jié)點(diǎn)部署是傳感器網(wǎng)絡(luò)進(jìn)行工作的第一步，它直接關(guān)系到網(wǎng)絡(luò)監(jiān)測(cè)信息的準(zhǔn)確性、完整性和時(shí)效性。合理的節(jié)點(diǎn)部署不僅可以提高網(wǎng)絡(luò)的工作效率，也是無(wú)線傳感器網(wǎng)絡(luò)研究領(lǐng)域的基本問(wèn)題之一。目前，關(guān)于節(jié)點(diǎn)部署的研究中，已經(jīng)設(shè)計(jì)出了許多模型和相關(guān)算法。這些技術(shù)可根據(jù)適用環(huán)境分為三類(lèi)：第一類(lèi)適用于采用確定放置的部署方式；第二類(lèi)適用于節(jié)點(diǎn)不具備移動(dòng)能力，而且采用隨機(jī)拋灑的部署方式；第三類(lèi)適用于節(jié)點(diǎn)具備移動(dòng)能力，采用隨機(jī)拋灑部署方式。

2.1.1 采用確定放置的部署技術(shù)

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

確定性部署通常應(yīng)用于網(wǎng)絡(luò)的狀態(tài)相對(duì)固定或應(yīng)用環(huán)境已知，節(jié)點(diǎn)在網(wǎng)絡(luò)中的位置信息以及節(jié)點(diǎn)的密度已知情況下。節(jié)點(diǎn)的確定性部署通過(guò)對(duì)問(wèn)題進(jìn)行學(xué)抽象，可成為靜態(tài)優(yōu)化問(wèn)題或線性規(guī)劃問(wèn)題[1]。在文獻(xiàn)［2］中，得出節(jié)點(diǎn)部署達(dá)到覆蓋所需要的最少節(jié)點(diǎn)個(gè)數(shù)并給出了節(jié)點(diǎn)相應(yīng)的位置；在文獻(xiàn)［3］中，利用多邊形網(wǎng)格來(lái)部署節(jié)點(diǎn)，以實(shí)現(xiàn)最大的連通覆蓋。確定性部署能簡(jiǎn)化問(wèn)題的解決方案，但在實(shí)際的應(yīng)用中，尤其是大規(guī)模、無(wú)人監(jiān)守的惡劣環(huán)境中，隨機(jī)部署顯得更具有優(yōu)勢(shì)。

2.1.2 采用隨機(jī)拋灑且節(jié)點(diǎn)不具移動(dòng)能力的部署技術(shù)

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

2.1.3 采用隨機(jī)拋灑且節(jié)點(diǎn)具移動(dòng)能力的部署技術(shù)

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