摘要：以無(wú)線傳感器網(wǎng)絡(luò)輔助節(jié)點(diǎn)為主要研究對(duì)象，利用Delaunay 三角剖分技術(shù)獲得網(wǎng)絡(luò)節(jié)點(diǎn)的基礎(chǔ)上，在傳感器網(wǎng)絡(luò)檢測(cè)的目標(biāo)區(qū)域內(nèi)含有一些覆蓋盲點(diǎn)的情況下，提出了一種能量有效的傳感器網(wǎng)絡(luò)輔助節(jié)點(diǎn)配置算法。利用模擬仿真試驗(yàn)表明，與原算法相比，該算法在網(wǎng)絡(luò)覆蓋率及算法運(yùn)行時(shí)間等方面更具一定的優(yōu)勢(shì)。

關(guān)鍵詞：輔助節(jié)點(diǎn);無(wú)線傳感器網(wǎng)絡(luò);Delaunay三角剖分;覆蓋盲點(diǎn)

中圖分類號(hào)：TP393 ? ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1009-3044（2019）14-0025-02

1 引言

無(wú)線傳感器網(wǎng)絡(luò)由大量傳感器節(jié)點(diǎn)組成，通常它們被密集地布置在要測(cè)量的環(huán)境中來(lái)獲取所需的數(shù)據(jù)信息。傳感器節(jié)點(diǎn)配置是無(wú)線傳感器網(wǎng)絡(luò)研究的核心問(wèn)題之一。無(wú)線傳感器節(jié)點(diǎn)被廣泛應(yīng)用于一些場(chǎng)景信息監(jiān)測(cè)中，為了提高無(wú)線傳感器網(wǎng)絡(luò)的靈活性，延長(zhǎng)網(wǎng)絡(luò)的生命周期，文獻(xiàn)[1]運(yùn)用 Delaunay三角剖分的策略定義了節(jié)點(diǎn)之間的鄰接關(guān)系，并且可以通過(guò) Delaunay三角剖分快速獲取節(jié)點(diǎn)的鄰接節(jié)點(diǎn)。文獻(xiàn)[2]和文獻(xiàn)[3]使用啟發(fā)式連通支配集算法思想來(lái)選擇活躍節(jié)點(diǎn)。文獻(xiàn)[4]使用Voronic劃分的減量構(gòu)造將部分覆蓋冗余節(jié)點(diǎn)轉(zhuǎn)入能耗較低的睡眠狀態(tài)，在能量效率、網(wǎng)絡(luò)聲明周期等方面得到了改進(jìn)。

本文在Delaunay三角剖分的連通算法基礎(chǔ)上，提出了一種改進(jìn)的輔助節(jié)點(diǎn)算法（CCV），該算法選擇一些節(jié)點(diǎn)輔助覆蓋構(gòu)成連通網(wǎng)絡(luò)，其中覆蓋節(jié)點(diǎn)和輔助節(jié)點(diǎn)都為活躍節(jié)點(diǎn)。改進(jìn)算法在網(wǎng)絡(luò)覆蓋率及算法運(yùn)行時(shí)間優(yōu)于原算法。

2 輔助節(jié)點(diǎn)構(gòu)造

改進(jìn)算法的Voronoi劃分Vor（R2，C）（如圖1（a）），構(gòu)造覆蓋集C的Delaunay三角剖分Del（C）（如圖1 （b））。使用算法BFS遍歷圖Del（C）中所有長(zhǎng)度不超過(guò)Rt的邊，獲得覆蓋集C所有的連通覆蓋子集，即每個(gè)連通覆蓋子集內(nèi)的任意兩節(jié)點(diǎn)之間存在一條由覆蓋節(jié)點(diǎn)組成的連通路徑，如圖1 （b）的實(shí)線所示;用Ci表示第i個(gè)連通覆蓋子集，每個(gè)覆蓋子集Ci抽象為虛擬節(jié)點(diǎn)vi，將覆蓋集C轉(zhuǎn)換為一個(gè)虛擬節(jié)點(diǎn)集V。如圖1（b）所示的圖Del（C），轉(zhuǎn)換后的虛擬節(jié)點(diǎn)集V為{v1，v2，v3，v4，v5}。

若V僅有一個(gè)虛擬節(jié)點(diǎn)，則覆蓋集C構(gòu)成連通網(wǎng)絡(luò);否則，按照如下步驟選擇輔助節(jié)點(diǎn)。

第一步：依據(jù)CCV算法的Voronoi劃分Vor（R2，S）和通信半徑Rt，構(gòu)造初始網(wǎng)絡(luò)的Unit Delaunay三角剖分UDel（S），如圖 2 所示。對(duì)圖UDel（S）的任意邊uv，按照公式cost（u，v）=||uv||a/max（eu，ev）b計(jì)算通信代價(jià)，其中max（eu，ev）表示節(jié)點(diǎn)u和v中剩余能量最大值，指數(shù)a和b為非負(fù)整數(shù)。

第二步：若UDG圖為連通圖，則UDel圖為UDG圖的連通子圖。將圖UDel（S）的每個(gè)連通覆蓋子集Ci抽象為虛擬節(jié)點(diǎn)vi，刪除連接節(jié)點(diǎn)集Ci中兩節(jié)點(diǎn)的邊;當(dāng)節(jié)點(diǎn)u?Ci與節(jié)點(diǎn)集Ci的m（?1）個(gè)節(jié)點(diǎn)連接時(shí)，保留通信代價(jià)最小的邊連接節(jié)點(diǎn)u和虛擬節(jié)點(diǎn)vi。經(jīng)過(guò)上述操作后，圖UDel（S）變換為一個(gè)連通加權(quán)圖，記為wUDel（S）。

第三步：Del圖一個(gè)連通圖，但一些邊的長(zhǎng)度超過(guò)Rt。將圖Del（C）的每個(gè)連通覆蓋子集Ci抽象為虛擬節(jié)點(diǎn)vi，刪除連接節(jié)點(diǎn)集Ci中兩節(jié)點(diǎn)的邊（即長(zhǎng)度不超過(guò)Rt的邊）;任意虛擬節(jié)點(diǎn)vi和vj，圖Del（C）存在m（?1）條邊連接覆蓋集Ci和Cj，保留一條邊連接虛擬節(jié)點(diǎn)vi和vj，將節(jié)點(diǎn)vi和vj在圖wUDel（S）中的最短路徑Path（vi，vj）上的通信代價(jià)作為該邊的權(quán)值。經(jīng)過(guò)上述操作后，圖Del（C）變換為一個(gè)連通加權(quán)圖Del（V），如圖3（a）所示。

第四步：使用Kruskal算法構(gòu)造Del（V）的最小生成樹(shù)Tree（V），每條邊對(duì)應(yīng)的最短路徑上的節(jié)點(diǎn)即為輔助覆蓋集C構(gòu)成網(wǎng)絡(luò)的節(jié)點(diǎn)，如圖 3（b） 所示。

3實(shí)驗(yàn)仿真分析

為了評(píng)估算法性能，本文用C++實(shí)現(xiàn)算法與文獻(xiàn)CVT+MST，其中算法CVT求解CVT覆蓋節(jié)點(diǎn)、算法MST求解MST網(wǎng)關(guān)節(jié)點(diǎn)。運(yùn)行環(huán)境為P2.0GHz CPU與2G內(nèi)存;實(shí)驗(yàn)場(chǎng)景如下：給定感知半徑Rs，在目標(biāo)區(qū)域1000×1000內(nèi)隨機(jī)部署n個(gè)互不重疊的傳感器節(jié)點(diǎn)。

理論上，覆蓋節(jié)點(diǎn)數(shù)量將與傳感半徑Rs有關(guān)，輔助覆蓋節(jié)點(diǎn)構(gòu)成連通網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)量將與通信半徑Rt有關(guān);為此，本文將針對(duì)不同的Rt/Rs值，統(tǒng)計(jì)評(píng)估活躍節(jié)點(diǎn)的數(shù)量、剩余能量和發(fā)射功率以及算法執(zhí)行時(shí)間等指標(biāo)。

3.1活躍節(jié)點(diǎn)的數(shù)量

1） 網(wǎng)絡(luò)覆蓋率是指所有網(wǎng)絡(luò)覆蓋目標(biāo)區(qū)域的面積比率。在目標(biāo)區(qū)域內(nèi)隨機(jī)部署1000～2000個(gè)節(jié)點(diǎn)，初始網(wǎng)絡(luò)的覆蓋率如圖×所示;當(dāng)Rs=50時(shí)，初始網(wǎng)絡(luò)的覆蓋率超過(guò)99.86%，但不會(huì)收斂到100%;當(dāng)Rs=100時(shí)，覆蓋率將近似收斂于100%;因此，在目標(biāo)區(qū)域內(nèi)含有一些覆蓋盲點(diǎn)的假設(shè)下，研究傳感器網(wǎng)絡(luò)的最小連通覆蓋具有很強(qiáng)的現(xiàn)實(shí)意義。

2） 改進(jìn)算法CCV求解覆蓋集時(shí)僅涉及傳感半徑Rs，即覆蓋集的大小由感知半徑Rs決定，如圖4所示;其中，Rs=50的覆蓋節(jié)點(diǎn)約為282，Rs=10的覆蓋節(jié)點(diǎn)約為72。當(dāng)Rs=100時(shí)，網(wǎng)絡(luò)可以覆蓋整個(gè)目標(biāo)區(qū)域時(shí)，算法CVT求解的覆蓋節(jié)點(diǎn)稍微大于CCV，但差值不到1;當(dāng)Rs=50時(shí)，網(wǎng)絡(luò)只能覆蓋部分目標(biāo)區(qū)域，算法CVT只能將所有節(jié)點(diǎn)設(shè)為覆蓋節(jié)點(diǎn)，其覆蓋節(jié)點(diǎn)明顯大于CCV。

3） 針對(duì)Rs=100的情況，分析Rc=50、100、150三種情況下的網(wǎng)關(guān)節(jié)點(diǎn)，如圖5所示。當(dāng)Rc=50，能夠相互通信的覆蓋節(jié)點(diǎn)不多。

當(dāng)Rs=100時(shí)，實(shí)驗(yàn)場(chǎng)景Rc=50、100、150的LCD網(wǎng)關(guān)節(jié)點(diǎn)分別約為155、33、0.4個(gè)，網(wǎng)絡(luò)部署密度基本上不影響LCD網(wǎng)關(guān)節(jié)點(diǎn)的大小，如圖5（a）所示。

隨著通信半徑Rc的增大，活躍節(jié)點(diǎn)中網(wǎng)關(guān)節(jié)點(diǎn)的比率RGS逐步減少，特別是Rc/Rs?1.5后的網(wǎng)關(guān)節(jié)點(diǎn)比率接近0，如圖5（b）所示?？偟膩?lái)說(shuō)， Rc/Rs<0.9時(shí)的MST網(wǎng)關(guān)節(jié)點(diǎn)小于LCD，而Rc/Rs?0.9后的LCD網(wǎng)關(guān)節(jié)點(diǎn)小于MST，其網(wǎng)關(guān)節(jié)點(diǎn)比率差<3%。

綜合圖5可知，給定感知半徑Rs與通信半徑Rc時(shí)，完全覆蓋目標(biāo)區(qū)域的活躍節(jié)點(diǎn)保持在一定的數(shù)量，與網(wǎng)絡(luò)部署密度無(wú)關(guān)，為此分析活躍節(jié)點(diǎn)的平均能量與平均度時(shí)將不考慮網(wǎng)絡(luò)部署密度。

3.2 算法運(yùn)行時(shí)間

隨著節(jié)點(diǎn)數(shù)量n的增加，CCV運(yùn)行時(shí)間將近似線性增長(zhǎng)，而CVT運(yùn)行時(shí)間將近似指數(shù)增長(zhǎng)，其中CCV運(yùn)行時(shí)間要低于CVT運(yùn)行時(shí)間將近102數(shù)量級(jí)，如圖6（a）所示。

4 展望

本文基于無(wú)線傳感器網(wǎng)絡(luò)配置輔助節(jié)點(diǎn)問(wèn)題，利用Delaunay 三角剖分獲得網(wǎng)絡(luò)節(jié)點(diǎn)，使用UDel圖的連通策略解決活躍節(jié)點(diǎn)的連通問(wèn)題。通過(guò)設(shè)置輔助節(jié)點(diǎn)，提升了節(jié)點(diǎn)的覆蓋質(zhì)量，在算法運(yùn)行時(shí)間方面得到了改善。以后的工作將綜合考慮傳感器網(wǎng)絡(luò)在選擇活躍節(jié)點(diǎn)時(shí)的網(wǎng)絡(luò)時(shí)延、通信干擾等問(wèn)題。

參考文獻(xiàn)：

[1] Yu X， Huang W， Lan J， et al. A Novel Virtual Force Approach for Node Deployment in Wireless Sensor Network[C] //IEEE， International Conference on Distributed Computing in Sensor Systems. IEEE Computer Society， 2012：359-363.

[2] Torkestani J A. An adaptive energy-efficient area coverage algorithm for wireless sensor networks[J].Ad Hoc Network，2013，11（6）：1655-1666.

[3] 張濤， 余翔宇， 藍(lán)俊健，等. 改進(jìn)的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)虛擬力部署方法[J]. 計(jì)算機(jī)應(yīng)用研究， 2015 （11） ：3356-3358.

[4] 徐鵬飛，廖明華，張華. 能量有效的傳感器網(wǎng)絡(luò)連通覆蓋控制算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2015，36（10）.

【通聯(lián)編輯：唐一東】