史佳琦，譚 勵(lì)，唐小江，連曉峰，王浩宇

（北京工商大學(xué)計(jì)算機(jī)與信息工程學(xué)院，北京 100048）

（*通信作者電子郵箱tanli@th.btbu.edu.cn）

0 引言

覆蓋優(yōu)化是傳感器網(wǎng)絡(luò)研究中的一個(gè)重要的問題，是指將傳感器放置在適當(dāng)?shù)奈恢?，使得傳感器覆蓋的區(qū)域能夠達(dá)到最大化，覆蓋優(yōu)化直接影響著傳感器網(wǎng)絡(luò)的性能。在未知的環(huán)境中部署大量的傳感器節(jié)點(diǎn)可以提高傳感器網(wǎng)絡(luò)的可擴(kuò)展性和可靠性［1］。對(duì)于覆蓋問題現(xiàn)在已經(jīng)有了很多的研究成果。Wang 等［2］提出了一種基于改進(jìn)鯨魚算法的無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化模型，實(shí)現(xiàn)了對(duì)感興趣區(qū)域的全覆蓋；Wang等［3］提出了一種基于粒子群優(yōu)化的覆蓋控制算法，先將傳感器節(jié)點(diǎn)隨機(jī)部署在目標(biāo)區(qū)域并保持靜止，然后，將傳感器網(wǎng)絡(luò)劃分成若干個(gè)小傳感器網(wǎng)絡(luò)并計(jì)算出每個(gè)小傳感器網(wǎng)絡(luò)的覆蓋率和能耗，最后根據(jù)每個(gè)劃分出的網(wǎng)格的覆蓋率和能耗對(duì)每個(gè)傳感器節(jié)點(diǎn)的感應(yīng)半徑進(jìn)行調(diào)整。樊富有等［4］利用量子遺傳算法研究了復(fù)雜的監(jiān)控環(huán)境下的無線視頻傳感網(wǎng)絡(luò)的覆蓋率問題，實(shí)驗(yàn)結(jié)果趨近于理想值；Habibi 等［5］使用基于梯度的非線性優(yōu)化方法為每個(gè)傳感器節(jié)點(diǎn)找到一個(gè)目標(biāo)點(diǎn)，從而盡可能增加局部的覆蓋率；何慶等［6］提出一種基于改進(jìn)正弦余弦算法的節(jié)點(diǎn)部署優(yōu)化方法，用較少的節(jié)點(diǎn)達(dá)到較高的覆蓋率。以上方法主要對(duì)傳感器節(jié)點(diǎn)的覆蓋率進(jìn)行了提升。

Lin 等［7］和Sung 等［8］研究了利用Voronoi 圖的方法在二維空間內(nèi)進(jìn)行自主部署的算法。Fang等［9］提出了基于盲區(qū)質(zhì)心的方案和基于干擾質(zhì)心的方案，用來解決移動(dòng)無線傳感器網(wǎng)絡(luò)中的覆蓋問題，在基于盲區(qū)質(zhì)心的方案中，每個(gè)傳感器的Voronoi 盲區(qū)多邊形首先是通過考慮相鄰位置來確定的，然后將Voronoi 盲區(qū)多邊形的質(zhì)心作為各傳感器的目標(biāo)位置。在基于干擾質(zhì)心的方案中，傳感器首先在每一輪中根據(jù)基于中心的方案找到覆蓋孔，然后在局部擾動(dòng)和局部重構(gòu)算子的作用下，移動(dòng)到目標(biāo)位置。Liao 等［10］對(duì)移動(dòng)無線傳感器中的連接問題進(jìn)行了研究，證實(shí)傳感器節(jié)點(diǎn)的移動(dòng)性對(duì)連通性和覆蓋率的影響。用Voronoi 劃分的方法估計(jì)網(wǎng)絡(luò)連接和目標(biāo)覆蓋所需要的傳感器節(jié)點(diǎn)的最小移動(dòng)量。Gao 等［11］詳細(xì)討論了可旋轉(zhuǎn)攝像機(jī)傳感器的全視野柵欄覆蓋問題，介紹了一種新的加權(quán)圖和兩種集中式算法，該方法節(jié)省了傳感器的節(jié)點(diǎn)個(gè)數(shù)同時(shí)也降低了時(shí)間復(fù)雜度。Li等［12］討論了有向傳感器和全向傳感器的覆蓋最大化移動(dòng)傳感器部署問題，得出同步旋轉(zhuǎn)運(yùn)動(dòng)控制和分級(jí)旋轉(zhuǎn)運(yùn)動(dòng)控制兩種算法的最優(yōu)性和復(fù)雜性結(jié)果。張軍等［13］提出了一種新的混合無線傳感器網(wǎng)絡(luò)覆蓋優(yōu)化算法，對(duì)固定節(jié)點(diǎn)進(jìn)行Voronoi 多邊形劃分；利用劃分結(jié)果分析固定節(jié)點(diǎn)的覆蓋盲區(qū)；利用基于反向?qū)W習(xí)策略的蜂群算法優(yōu)化部署移動(dòng)節(jié)點(diǎn)。林祝亮等［14］在網(wǎng)絡(luò)覆蓋率最優(yōu)化的同時(shí)，有效減少網(wǎng)絡(luò)迭代次數(shù)。在粒子進(jìn)化的多粒子群算法的基礎(chǔ)上提出了一種無線傳感網(wǎng)絡(luò)覆蓋優(yōu)化策略，通過多種群并行搜索，采取粒子進(jìn)化理論使陷入局部最優(yōu)的粒子迅速跳出，有效地避免了基本粒子群算法容易出現(xiàn)的“早熟”問題，提高了算法的穩(wěn)定性。這些方法使用Voronoi 的方法在提高傳感器節(jié)點(diǎn)覆蓋率的同時(shí)考慮了算法的復(fù)雜度，但節(jié)點(diǎn)的迭代時(shí)間普遍較長(zhǎng)，部署的復(fù)雜度也較高。

針對(duì)二維平面中的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的部署問題，本文在Voronoi 圖算法的基礎(chǔ)上提出了一種基于小結(jié)構(gòu)體的無線傳感器網(wǎng)絡(luò)部署算法（Deployment Algorithm based on Basic Architecture，DABA），由于不同結(jié)構(gòu)體之間存在孔洞問題，在覆蓋率與Voronoi圖算法覆蓋率相近情況下，該算法能夠提升部署效率，并且可以實(shí)現(xiàn)傳感器節(jié)點(diǎn)部署過程中的避障。

1 基于小結(jié)構(gòu)體的部署算法

1.1 小結(jié)構(gòu)體描述

在傳感器網(wǎng)絡(luò)的部署中一般要求被部署的節(jié)點(diǎn)數(shù)量有一定的規(guī)模，使節(jié)點(diǎn)最終能夠進(jìn)行密集的覆蓋，以此來避免在部署區(qū)域中出現(xiàn)覆蓋漏洞。

由于二維部署區(qū)域較為廣泛，而且單個(gè)傳感器節(jié)點(diǎn)的能力有限，要使傳感器節(jié)點(diǎn)能夠覆蓋到整個(gè)部署區(qū)域要求的節(jié)點(diǎn)數(shù)量很大，這會(huì)增加部署算法的復(fù)雜程度以及節(jié)點(diǎn)所需的迭代時(shí)間。為了解決這個(gè)問題，提出了“小結(jié)構(gòu)體”的概念。小結(jié)構(gòu)體是在應(yīng)對(duì)復(fù)雜監(jiān)測(cè)任務(wù)的時(shí)候，由若干個(gè)傳感器節(jié)點(diǎn)組成，具備典型特征的最小結(jié)構(gòu)單元。小結(jié)構(gòu)體在部署過程中被當(dāng)作一個(gè)整體進(jìn)行部署，小結(jié)構(gòu)體的內(nèi)部結(jié)構(gòu)不進(jìn)行改變，整個(gè)無線傳感器網(wǎng)絡(luò)由若干個(gè)小結(jié)構(gòu)體組成，共同完成復(fù)雜的監(jiān)測(cè)任務(wù)。小結(jié)構(gòu)體沒有一個(gè)固定的結(jié)構(gòu)，需要根據(jù)無線傳感器網(wǎng)絡(luò)的應(yīng)用環(huán)境以及監(jiān)測(cè)目標(biāo)的特征和監(jiān)測(cè)任務(wù)的復(fù)雜程度等各個(gè)方面進(jìn)行綜合考慮，設(shè)計(jì)適用于不同環(huán)境、不同監(jiān)測(cè)任務(wù)的小結(jié)構(gòu)體。

小結(jié)構(gòu)體定義 采用六邊形作為小結(jié)構(gòu)體的基本結(jié)構(gòu)。小結(jié)構(gòu)體由7 個(gè)傳感器節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)放置的位置分別對(duì)應(yīng)六邊形的6 個(gè)定點(diǎn)以及六邊形的中心點(diǎn)。選擇一個(gè)節(jié)點(diǎn)作為中心節(jié)點(diǎn)，通過中心節(jié)點(diǎn)來確定其余6 個(gè)成員節(jié)點(diǎn)的具體位置，如圖1 所示。在本文中選取S1為中心節(jié)點(diǎn)，小結(jié)構(gòu)體的邊長(zhǎng)。圖2為基于六邊形的小結(jié)構(gòu)體的仿真。

圖1 基于六邊形的小結(jié)構(gòu)體Fig.1 A basic architecture based on hexagon

圖2 基于六邊形的小結(jié)構(gòu)體仿真Fig.2 Simulation of basic architecture based on hexagon

設(shè)節(jié)點(diǎn)S1的坐標(biāo)為(xS1，yS1)，則小結(jié)構(gòu)體的中心P點(diǎn)的坐標(biāo)計(jì)算公式如式（1）所示：

由P點(diǎn)坐標(biāo)可以得到小結(jié)構(gòu)體的中心坐標(biāo)與小結(jié)構(gòu)體其他成員節(jié)點(diǎn)坐標(biāo)的映射關(guān)系，如式（2）所示：

其中i的取值范圍為｛1，2，3，4，5，6，7｝。

假設(shè)當(dāng)前節(jié)點(diǎn)的坐標(biāo)為Ci(xCi，yCi)，該節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合的定義如式（3）所示：

其中：D(i，j)為節(jié)點(diǎn)Ci與節(jié)點(diǎn)Cj之間的歐氏距離；Dth為臨界距離，決定兩個(gè)傳感器節(jié)點(diǎn)是否互為鄰居節(jié)點(diǎn)。D(i，j)的計(jì)算公式如式（4）所示：

具體構(gòu)建方法步驟如下：

1）對(duì)所有的傳感器節(jié)點(diǎn)構(gòu)建一個(gè)新的集合，用來存放節(jié)點(diǎn)。

2）標(biāo)記每一個(gè)節(jié)點(diǎn)的狀態(tài)，如果狀態(tài)值為True則代表該節(jié)點(diǎn)沒有與其他節(jié)點(diǎn)組成小結(jié)構(gòu)體；如果狀態(tài)值為False則代表該節(jié)點(diǎn)已經(jīng)與其他節(jié)點(diǎn)構(gòu)成小結(jié)構(gòu)體。

3）遍歷所有節(jié)點(diǎn)，判斷當(dāng)前節(jié)點(diǎn)的狀態(tài)信息，如果當(dāng)前節(jié)點(diǎn)的狀態(tài)值為True，則轉(zhuǎn)到步驟4）；如果當(dāng)前節(jié)點(diǎn)的狀態(tài)值為False，則轉(zhuǎn)到步驟8）。

4）遍歷當(dāng)前節(jié)點(diǎn)的所有鄰居節(jié)點(diǎn)的集合，統(tǒng)計(jì)鄰居節(jié)點(diǎn)集合中狀態(tài)值為True 的節(jié)點(diǎn)的個(gè)數(shù)，如果狀態(tài)值為True 的鄰居節(jié)點(diǎn)的個(gè)數(shù)小于7，轉(zhuǎn)到步驟7）；如果狀態(tài)值為True的鄰居節(jié)點(diǎn)的個(gè)數(shù)大于等于7，轉(zhuǎn)到步驟5）。

5）當(dāng)前的節(jié)點(diǎn)與鄰居節(jié)點(diǎn)集合中的前7個(gè)狀態(tài)值為True的鄰居節(jié)點(diǎn)構(gòu)成小結(jié)構(gòu)體，指定當(dāng)前的節(jié)點(diǎn)為中心節(jié)點(diǎn)，構(gòu)建基于六邊形的小結(jié)構(gòu)體，然后轉(zhuǎn)到步驟7）。

6）將所有已經(jīng)參與構(gòu)建小結(jié)構(gòu)體的節(jié)點(diǎn)的狀態(tài)值修改為False。

7）如果已經(jīng)遍歷完所有的節(jié)點(diǎn)，則轉(zhuǎn)到步驟8）；否則，遍歷下一個(gè)節(jié)點(diǎn)，轉(zhuǎn)到步驟3）。

8）結(jié)束退出。

1.2 DABA

本文提出的DABA 根據(jù)小結(jié)構(gòu)體中心位置以及小結(jié)構(gòu)體的半徑構(gòu)建二維Voronoi 圖，計(jì)算每個(gè)小結(jié)構(gòu)體所對(duì)應(yīng)的Voronoi 區(qū)域的中心位置，使小結(jié)構(gòu)體的中心位置移動(dòng)到對(duì)應(yīng)的Voronoi區(qū)域的中心，然后通過小結(jié)構(gòu)體的中心與其他成員節(jié)點(diǎn)之間的映射關(guān)系，計(jì)算每個(gè)成員節(jié)點(diǎn)的位置，多次迭代完成部署。

具體的部署算法如算法1所示。

算法1 DABA。

輸入：節(jié)點(diǎn)的個(gè)數(shù)N、節(jié)點(diǎn)的感知半徑r、互為鄰居節(jié)點(diǎn)的臨界距離Dth以及區(qū)域的邊界B；

輸出：節(jié)點(diǎn)最終位置C'。

文獻(xiàn)［12］提到的二維Voronoi 圖構(gòu)造的時(shí)間復(fù)雜度為O(nlogn)，本算法的時(shí)間復(fù)雜度為O(mn2logn)，n為節(jié)點(diǎn)的個(gè)數(shù)，m為迭代的次數(shù)。

1.3 避障設(shè)計(jì)

針對(duì)在實(shí)際部署中可能會(huì)出現(xiàn)障礙的情況，算法設(shè)置障礙點(diǎn)，作為實(shí)際部署環(huán)境中可能會(huì)出現(xiàn)的不能進(jìn)行部署障礙點(diǎn)的模擬。障礙點(diǎn)是在構(gòu)建完小結(jié)構(gòu)體之后添加的一個(gè)點(diǎn)，這個(gè)點(diǎn)和其他節(jié)點(diǎn)不同，它在整個(gè)部署過程中是不動(dòng)的且不能與其他節(jié)點(diǎn)組成小結(jié)構(gòu)體，同時(shí)其他節(jié)點(diǎn)在部署過程中要避開這個(gè)點(diǎn)。障礙點(diǎn)可以看作一個(gè)特殊的單獨(dú)節(jié)點(diǎn)。

2 仿真與結(jié)果分析

2.1 仿真實(shí)驗(yàn)

本文實(shí)驗(yàn)采用Python2.7 作為仿真環(huán)境，CPU 型號(hào)為Inter Core i7 6700T，監(jiān)測(cè)區(qū)域大小設(shè)置為200 m ×200 m 的二維平面，初始時(shí)，所有節(jié)點(diǎn)隨機(jī)部署在整個(gè)二維監(jiān)測(cè)區(qū)域內(nèi)，障礙點(diǎn)通過固定坐標(biāo)的方式添加到二維平面中，節(jié)點(diǎn)的感知半徑為5 m，障礙點(diǎn)的半徑為15 m，節(jié)點(diǎn)個(gè)數(shù)為602。仿真實(shí)驗(yàn)中涉及到的相關(guān)參數(shù)如表1中所示。

表1 實(shí)驗(yàn)參數(shù)Tab.1 Experimental parameters

本實(shí)驗(yàn)選取四組不同Dth值進(jìn)行仿真，Dth的值分別為10、15、20和1 000四個(gè)取值，分別用兩倍的感知半徑、三倍的感知半徑、四倍的感知半徑和全區(qū)域內(nèi)所有節(jié)點(diǎn)互為鄰居節(jié)點(diǎn)這五種情況。通過構(gòu)建小結(jié)構(gòu)體，采用二維Voronoi圖的方法在二維平面的目標(biāo)監(jiān)測(cè)區(qū)域內(nèi)完成部署算法以及小結(jié)構(gòu)體繞開障礙點(diǎn)的情況的仿真。未與其他節(jié)點(diǎn)組成小結(jié)構(gòu)體的單個(gè)節(jié)點(diǎn)，視為一種特殊的小結(jié)構(gòu)體，單個(gè)節(jié)點(diǎn)與其他小結(jié)構(gòu)體同等級(jí)別參與部署算法。圖3 為Dth=10時(shí)節(jié)點(diǎn)的部署情況以及躲避障礙點(diǎn)的情況。

圖3 Dth=10的部署情況Fig.3 Deployment situation with Dth=10

2.2 結(jié)果分析

本文主要通過以下3 個(gè)指標(biāo)對(duì)所提出算法的性能進(jìn)行評(píng)估：

覆蓋率 判斷傳感器網(wǎng)絡(luò)性能十分重要的一個(gè)指標(biāo)，反映了傳感器網(wǎng)絡(luò)對(duì)于所需監(jiān)測(cè)區(qū)域中監(jiān)測(cè)對(duì)象的全面監(jiān)測(cè)能力：

部署時(shí)間 指的是在整個(gè)部署的過程中，使節(jié)點(diǎn)盡可能多地覆蓋區(qū)域，也就是當(dāng)覆蓋率達(dá)到一個(gè)相對(duì)穩(wěn)定狀態(tài)時(shí)所需要的時(shí)間，由于涉及的兩種算法都需要先構(gòu)造Voronoi區(qū)域且所需時(shí)間差別不大，部署時(shí)間從節(jié)點(diǎn)開始移動(dòng)時(shí)，即節(jié)點(diǎn)開始迭代時(shí)算起：

移動(dòng)距離 指的是在整個(gè)部署的過程中，節(jié)點(diǎn)在部署時(shí)間內(nèi)進(jìn)行移動(dòng)的距離，即節(jié)點(diǎn)從初始的地點(diǎn)到最終部署情況的地點(diǎn)所移動(dòng)的距離：

其中：xfinal、xinitial為節(jié)點(diǎn)最終橫坐標(biāo)、節(jié)點(diǎn)初始橫坐標(biāo)；yfinal、yinitial為節(jié)點(diǎn)最終縱坐標(biāo)、節(jié)點(diǎn)初始縱坐標(biāo)。

從圖3 的最終部署情況看出基于小結(jié)構(gòu)體的部署算法能夠較好地對(duì)二維平面進(jìn)行覆蓋，Dth=10 的情況下部署效果最佳，這說明DABA 能夠較好地對(duì)需要部署的二維平面進(jìn)行部署，但要依據(jù)部署情況選擇互為鄰居節(jié)點(diǎn)的臨界值以便能夠達(dá)到更好的部署效果。躲避障礙的情況中互為鄰居節(jié)點(diǎn)的臨界值為兩倍半徑，即Dth=10 的情況下小結(jié)構(gòu)體躲避障礙點(diǎn)的效果最佳，節(jié)點(diǎn)可以全部躲避開障礙點(diǎn)后進(jìn)行部署。

圖4 為Dth=15、Dth=20 以及Dth=1 000 的情況下節(jié)點(diǎn)的最終部署情況以及躲避障礙點(diǎn)的情況。

圖4 最終部署及躲避障礙點(diǎn)的情況Fig.4 Final deployment and obstacle avoidance situation

在互為鄰居節(jié)點(diǎn)的臨界值分別為Dth=15、Dth=20 和Dth=1 000 的三種情況下都存在有節(jié)點(diǎn)不能完全避開障礙點(diǎn)的情況，并且從對(duì)比圖中可以看出，在基于小結(jié)構(gòu)體的二維部署情況下，參與部署的節(jié)點(diǎn)的個(gè)數(shù)越多，節(jié)點(diǎn)躲避障礙點(diǎn)的效果越好。

下面將從覆蓋率、部署時(shí)間以及移動(dòng)距離這三個(gè)指標(biāo)分別將基于小結(jié)構(gòu)體的二維部署算法與Voronoi 圖方法進(jìn)行對(duì)比，驗(yàn)證本文中所提出算法的有效性。

在圖5中，將二維Voronoi 圖方法和本文提出的基于小結(jié)構(gòu)體方法的四種情況進(jìn)行了對(duì)比。其中：3dDABA-A表示Dth=10，3dDABA-B 表示Dth=15，3dDABA-C 表示Dth=20，3dDABA-D表示Dth=1 000。從圖5 可以看出，當(dāng)?shù)螖?shù)不斷增多的時(shí)候，基于小結(jié)構(gòu)體算法中的四種情況的覆蓋率都逐漸增大，最終區(qū)域平衡。雖然覆蓋率低于Voronoi 圖方法但差距不大。當(dāng)Dth=10時(shí)的覆蓋率最大，能夠達(dá)到92%左右。

圖5 覆蓋率變化圖Fig.5 Coverage rate change diagram

圖6中將二維Voronoi 圖方法和文中提出的基于小結(jié)構(gòu)體方法的四種情況下算法再部署過程中每個(gè)節(jié)點(diǎn)每次迭代的平均移動(dòng)距離進(jìn)行了對(duì)比。從圖6中可以看出，隨著迭代次數(shù)的不斷增加，四種情況下每個(gè)節(jié)點(diǎn)的平均移動(dòng)距離都在不斷減小，最終趨近于0，算法最終收斂。每個(gè)節(jié)點(diǎn)在部署過程中都不斷趨于靜止，表明網(wǎng)絡(luò)在逐漸達(dá)到一個(gè)穩(wěn)定的狀態(tài)。從結(jié)果中看雖然本文提出的算法中節(jié)點(diǎn)的平均移動(dòng)距離高于二維Voronoi圖方法的移動(dòng)距離，但是差距并不是很明顯。

圖6 每個(gè)節(jié)點(diǎn)每次迭代平均移動(dòng)距離Fig.6 Average travel distance of different nodes in each iteration

圖7 將二維Voronoi 圖方法和文中提出的基于小結(jié)構(gòu)體方法的四種情況下的節(jié)點(diǎn)迭代的部署時(shí)間進(jìn)行了對(duì)比。從圖7中可以看出，基于小結(jié)構(gòu)體的部署算法在節(jié)點(diǎn)迭代的部署時(shí)間方面的優(yōu)勢(shì)較為突出。與二維Voronoi圖方法相比較：互為鄰居節(jié)點(diǎn)的臨界值為兩倍半徑，即Dth=10 情況下算法節(jié)點(diǎn)迭代的部署時(shí)間是它的1/3；互為鄰居節(jié)點(diǎn)的臨界值為三倍半徑，即Dth=15 情況下的算法節(jié)點(diǎn)迭代的部署時(shí)間是它的1/9；互為鄰居節(jié)點(diǎn)的臨界值為四倍半徑（Dth=20）和互為鄰居節(jié)點(diǎn)的臨界值不限（Dth=1 000）的算法節(jié)點(diǎn)迭代的部署時(shí)間更是遠(yuǎn)遠(yuǎn)小于Voronoi圖方法的部署時(shí)間。

圖7 部署時(shí)間隨迭代次數(shù)變化Fig.7 Deployment time varying with number of iterations

在圖8中，通過將二維Voronoi 圖方法中節(jié)點(diǎn)個(gè)數(shù)與文中提出的基于小結(jié)構(gòu)體的方法的四種情況中小結(jié)構(gòu)體的個(gè)數(shù)進(jìn)行了對(duì)比。從圖8中可以看出，構(gòu)造小結(jié)構(gòu)體之后，參與構(gòu)造Voronoi 圖的節(jié)點(diǎn)數(shù)量有了很大幅度的下降，因此這能夠有效地降低構(gòu)造Voronoi 圖的復(fù)雜度，從而降低整個(gè)算法的復(fù)雜度。在仿真實(shí)驗(yàn)中：在互為鄰居節(jié)點(diǎn)的臨界值為四倍半徑，即Dth=20 情況下參與構(gòu)造Voronoi 圖節(jié)點(diǎn)的數(shù)量約為二維Voronoi 圖方法中參與構(gòu)造Voronoi 圖節(jié)點(diǎn)數(shù)量的1/3；互為鄰居節(jié)點(diǎn)的臨界值不限，即Dth=1 000情況下參與構(gòu)造Voronoi圖節(jié)點(diǎn)的數(shù)量約為Voronoi 圖方法中參與構(gòu)造Voronoi 圖節(jié)點(diǎn)數(shù)量的1/6。

通過仿真結(jié)果的比較，可以發(fā)現(xiàn)文中所提出的算法在部署時(shí)間這一方面有著非常明顯的優(yōu)勢(shì)，覆蓋率在某些情況下可以超過Voronoi 圖方法，雖然覆蓋率不及Voronoi 圖方法但差距并不明顯。節(jié)點(diǎn)每次迭代的平均移動(dòng)距離方面高于二維Voronoi 圖方法的移動(dòng)距離，但是差距并不是很明顯。通過綜合部署時(shí)間、覆蓋率以及平均移動(dòng)距離這三個(gè)衡量指標(biāo)，可以發(fā)現(xiàn)，當(dāng)互為鄰居節(jié)點(diǎn)的臨界值為兩倍半徑，即Dth=10情況和互為鄰居節(jié)點(diǎn)的臨界值為三倍半徑，即Dth=15 情況時(shí)的這兩個(gè)方案效果是最好的。在實(shí)際部署情況中可根據(jù)部署節(jié)點(diǎn)數(shù)量以及需要覆蓋情況和要求完成時(shí)間選擇Dth值，盡可能減小臨界值，使覆蓋率更高。

圖8 不同條件下小結(jié)構(gòu)體個(gè)數(shù)Fig.8 The number of basic architectures under different conditions

3 結(jié)語

針對(duì)二維平面中的無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的部署問題，本文提出了基于小結(jié)構(gòu)體的無線傳感器網(wǎng)絡(luò)部署算法（DABA），提出了小結(jié)構(gòu)體的概念，通過仿真實(shí)驗(yàn)分析了算法的覆蓋率、部署時(shí)間以及移動(dòng)距離，并與二維Voronoi 圖方法進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明本文算法在部署時(shí)間上有明顯的優(yōu)勢(shì)，同時(shí)可以減少參與構(gòu)造Voronoi 圖的節(jié)點(diǎn)數(shù)量，有效地降低構(gòu)造Voronoi圖的復(fù)雜度，從而降低整個(gè)算法的復(fù)雜度。下一步將研究三維或其他復(fù)雜的環(huán)境中節(jié)點(diǎn)的部署方法。