一種改進Delaunay三角剖分的輔助節點算法研究

摘要：以無線傳感器網絡輔助節點為主要研究對象，利用Delaunay 三角剖分技術獲得網絡節點的基礎上，在傳感器網絡檢測的目標區域內含有一些覆蓋盲點的情況下，提出了一種能量有效的傳感器網絡輔助節點配置算法。利用模擬仿真試驗表明，與原算法相比，該算法在網絡覆蓋率及算法運行時間等方面更具一定的優勢。

關鍵詞：輔助節點;無線傳感器網絡;Delaunay三角剖分;覆蓋盲點

中圖分類號：TP393 ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2019）14-0025-02

1 引言

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

本文在Delaunay三角剖分的連通算法基礎上，提出了一種改進的輔助節點算法（CCV），該算法選擇一些節點輔助覆蓋構成連通網絡，其中覆蓋節點和輔助節點都為活躍節點。改進算法在網絡覆蓋率及算法運行時間優于原算法。

2 輔助節點構造

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

若V僅有一個虛擬節點，則覆蓋集C構成連通網絡;否則，按照如下步驟選擇輔助節點。

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

第二步：若UDG圖為連通圖，則UDel圖為UDG圖的連通子圖。將圖UDel（S）的每個連通覆蓋子集Ci抽象為虛擬節點vi，刪除連接節點集Ci中兩節點的邊;當節點u?Ci與節點集Ci的m（?1）個節點連接時，保留通信代價最小的邊連接節點u和虛擬節點vi。經過上述操作后，圖UDel（S）變換為一個連通加權圖，記為wUDel（S）。

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

第四步：使用Kruskal算法構造Del（V）的最小生成樹Tree（V），每條邊對應的最短路徑上的節點即為輔助覆蓋集C構成網絡的節點，如圖 3（b） 所示。

3實驗仿真分析

為了評估算法性能，本文用C++實現算法與文獻CVT+MST，其中算法CVT求解CVT覆蓋節點、算法MST求解MST網關節點。運行環境為P2.0GHz CPU與2G內存;實驗場景如下：給定感知半徑Rs，在目標區域1000×1000內隨機部署n個互不重疊的傳感器節點。

理論上，覆蓋節點數量將與傳感半徑Rs有關，輔助覆蓋節點構成連通網絡的節點數量將與通信半徑Rt有關;為此，本文將針對不同的Rt/Rs值，統計評估活躍節點的數量、剩余能量和發射功率以及算法執行時間等指標。

3.1活躍節點的數量

1） 網絡覆蓋率是指所有網絡覆蓋目標區域的面積比率。在目標區域內隨機部署1000～2000個節點，初始網絡的覆蓋率如圖×所示;當Rs=50時，初始網絡的覆蓋率超過99.86%，但不會收斂到100%;當Rs=100時，覆蓋率將近似收斂于100%;因此，在目標區域內含有一些覆蓋盲點的假設下，研究傳感器網絡的最小連通覆蓋具有很強的現實意義。

2） 改進算法CCV求解覆蓋集時僅涉及傳感半徑Rs，即覆蓋集的大小由感知半徑Rs決定，如圖4所示;其中，Rs=50的覆蓋節點約為282，Rs=10的覆蓋節點約為72。當Rs=100時，網絡可以覆蓋整個目標區域時，算法CVT求解的覆蓋節點稍微大于CCV，但差值不到1;當Rs=50時，網絡只能覆蓋部分目標區域，算法CVT只能將所有節點設為覆蓋節點，其覆蓋節點明顯大于CCV。

3） 針對Rs=100的情況，分析Rc=50、100、150三種情況下的網關節點，如圖5所示。當Rc=50，能夠相互通信的覆蓋節點不多。

當Rs=100時，實驗場景Rc=50、100、150的LCD網關節點分別約為155、33、0.4個，網絡部署密度基本上不影響LCD網關節點的大小，如圖5（a）所示。

隨著通信半徑Rc的增大，活躍節點中網關節點的比率RGS逐步減少，特別是Rc/Rs?1.5后的網關節點比率接近0，如圖5（b）所示。總的來說， Rc/Rs<0.9時的MST網關節點小于LCD，而Rc/Rs?0.9后的LCD網關節點小于MST，其網關節點比率差<3%。

綜合圖5可知，給定感知半徑Rs與通信半徑Rc時，完全覆蓋目標區域的活躍節點保持在一定的數量，與網絡部署密度無關，為此分析活躍節點的平均能量與平均度時將不考慮網絡部署密度。

3.2 算法運行時間

隨著節點數量n的增加，CCV運行時間將近似線性增長，而CVT運行時間將近似指數增長，其中CCV運行時間要低于CVT運行時間將近102數量級，如圖6（a）所示。

4 展望

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

參考文獻：

[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] 張濤， 余翔宇， 藍俊健，等. 改進的無線傳感器網絡節點虛擬力部署方法[J]. 計算機應用研究， 2015 （11） ：3356-3358.

[4] 徐鵬飛，廖明華，張華. 能量有效的傳感器網絡連通覆蓋控制算法[J].小型微型計算機系統，2015，36（10）.

【通聯編輯：唐一東】