基于小結(jié)構(gòu)體的無線傳感器網(wǎng)絡(luò)部署算法

史佳琦，譚 勵，唐小江，連曉峰，王浩宇

（北京工商大學計算機與信息工程學院，北京 100048）

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

0 引言

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

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

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

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

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

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

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

小結(jié)構(gòu)體定義 采用六邊形作為小結(jié)構(gòu)體的基本結(jié)構(gòu)。小結(jié)構(gòu)體由7 個傳感器節(jié)點組成，每個節(jié)點放置的位置分別對應(yīng)六邊形的6 個定點以及六邊形的中心點。選擇一個節(jié)點作為中心節(jié)點，通過中心節(jié)點來確定其余6 個成員節(jié)點的具體位置，如圖1 所示。在本文中選取S1為中心節(jié)點，小結(jié)構(gòu)體的邊長。圖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é)點S1的坐標為(xS1，yS1)，則小結(jié)構(gòu)體的中心P點的坐標計算公式如式（1）所示：

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

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

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

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

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

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

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

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

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

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

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

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

8）結(jié)束退出。

1.2 DABA

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

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

算法1 DABA。

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

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

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

1.3 避障設(shè)計

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

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

2.1 仿真實驗

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

表1 實驗參數(shù)Tab.1 Experimental parameters

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

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

2.2 結(jié)果分析

本文主要通過以下3 個指標對所提出算法的性能進行評估：

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

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

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

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

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

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

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

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

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

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

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

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

圖6 每個節(jié)點每次迭代平均移動距離Fig.6 Average travel distance of different nodes in each iteration

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

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

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

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

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

3 結(jié)語

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