基于三角形斯坦納樹的分區連通性恢復算法*

秦寧寧，吳德恩，余穎華（.江南大學物聯網工程學院，江蘇無錫2422；2.江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫2422）

?

基于三角形斯坦納樹的分區連通性恢復算法*

秦寧寧1，2*，吳德恩1，余穎華1
（1.江南大學物聯網工程學院，江蘇無錫214122；2.江南大學輕工過程先進控制教育部重點實驗室，江蘇無錫214122）

摘要：無線傳感器網絡中的節點由于自身能量的消耗，及外部因素影響會導致節點出現大規模的失效，從而把無線傳感器網絡分割成幾個獨立的不能相互通信的分區。為恢復網絡，重建分區之間的通信鏈路，提出基于三角形斯坦納樹連通恢復算法。該算法首先利用傳統算法實現分區連通，然后通過構建三角形斯坦納樹以減少部署的中繼節點數量。與現有的一些算法相比，該方法形成的網絡拓撲不僅減少了部署中繼節點的數量，能夠使分區重新連通，而且能夠減少網絡通信的能量消耗。實驗結果表明，所提方法相對于傳統算法在構建網絡拓撲時更加有效。

關鍵詞：無線傳感器網絡；連通性；三角形斯坦納樹；分區

項目來源：江蘇省“六大人才高峰”第十一批高層次人才項目（DZXX-026）；2014年國家公派高級研究學者及訪問學者（含博士后）項目；國家自然科學基金項目（61304264）；江蘇高校優勢學科建設工程項目；江蘇省產學研聯合創新資金前瞻性聯合研究項目（BY2014023-31）；中央高校基本科研業務費專項資金項目（JUSRP51510）

無線傳感器網絡中的節點具有體積小、成本低等特點［1-3］，在提高網絡應用靈活性的同時，也決定了節點不可能攜帶可供長期使用的能量模塊。在惡劣的環境下，能量有限的節點很容易受自然環境或人為因素的影響而出現大規模的損壞［4-6］，造成網絡分割成獨立分區而不能相互通信，從而喪失了監測能力。因此，恢復網絡的連通性成為一個至關重要的研究課題［7］。

在恢復受損網絡的連通性工作中，部署中繼節點無疑是一個快速有效的方法［8］。通常中繼節點擁有比普通節點更多的能量，更遠的通信范圍［9］，以其作為各個分離分區之間的重建橋梁，可以解決分區之間的連通性問題［10］。在中繼修復過程中，最關鍵的問題是如何能部署更少的中繼節點同時確保相互獨立的分區能重新進行通信［11］。

為了以更少的中繼節點恢復分區的連通性，許多啟發式方法已經被提出。文獻［7］提出通過重置失效節點的鄰居位置來恢復網絡連通，然而這種方法不能處理多節點同時失效情況，且不能處理部分區域內節點不能移動的情況。文獻［12］中的MST_ 1TRNP（Minimum Spanning Trees Algorithm Based on a Single-Tiered Relay Node Placement）算法采用krus?kal或prim算法尋找最小生成樹，根據邊長與中繼節點通信半徑，沿著樹的邊部署中繼節點恢復連通，但該方法復雜度較高，且恢復后網絡的節點平均連通度較低。為了提高節點平均連通度，單連通蜘蛛網1C-SpiderWeb（1-Connected Spiderweb）算法［13］通過形成一個類似于蜘蛛網的網絡結構完成中繼節點布置，雖然提高了節點平均連通度，但大量中繼節點的布置代價降低了網絡效率，增大了分區間數據傳輸延遲。基于網格優化的分布式中繼節點布置算法［14］CORP（Cell-based Optimized Relay node Placement al?gorithm）將網絡劃分為大小相等的網格單元，根據分區所在網格位置，由外向內畫長方形找到最短路徑，布置額外節點重建各個分區連接。所形成的網絡拓撲能均衡網絡數據傳輸量，降低了分區間數據傳輸延遲，但復雜度較高，不適合在大規模網絡中使用。

為克服調度中繼節點補位過程中，在復雜度、效率、數據傳輸延遲等多方面性能難于兼顧的問題。論文提出了基于三角形斯坦納樹連通性恢復算法CRATST（Connectivity Recovery Algorithm based on Triangle Steiner Tree），通過引入斯坦納點，構造三角形斯坦納樹，減少恢復分區連通性所需的中繼節點數量，降低分區間通信的距離與能量消耗，提高網絡的性能。

1　網絡描述

1.1網絡模型

在給定空間A內部署的傳感器網絡S={Si| i=1,2,?,N}遭受到大規模的破壞后，可能會被分裂成若干無法直接通信的子區域。如圖1所示，灰色圓點表示失效節點，白色圓點表示正常工作節點，若將能正常工作節點形成的孤立網絡稱為分區，則圖1中存在7個分區，并以Segi代表第i個分區，i=1,2,?,Nseg，其中Nseg為分區數量。顯然，分區內的節點能夠相互進行通信，分區間不能通信。

不失一般性，設定網絡為靜態同構網絡，即所有節點具有相同的感知半徑r和通信半徑R。部署的中繼節點與已有節點具有相同的感知半徑和通信半徑。節點可以利用已有的定位算法獲得自身位置信息［15］。

圖1　網絡受破壞后，形成獨立分區

1.2相關知識與定義

定義1三角形的斯坦納點：三角形內到三頂點距離之和最小的點即為三角形的斯坦納點［16］。

對于給定網絡S，任意三個相鄰的節點Si,Sj,Sk構成三角形△SiSjSk，且其中不包含其它節點。若△SiSjSk中存在斯坦納點Q，根據文獻［16］關于三角形斯坦納點的位置特征，結合△SiSjSk的內角大小，Q的位置可基于如下2種情況進行確定。

①∠SiSjSk,SjSiSk,SiSkSj<

若∠SiSjSk,SjSiSk,SiSkSj<，根據文獻［16］可知，點Q必在三角形內，且與△SiSjSk任意兩點連線的夾角均為，如圖2（a）所示，即式（1）成立。

則基于式（1），可確定斯坦納點Q的坐標。

若△SiSjSk中存在某內角∠SiSjSk≥，根據文獻［16］可知，其斯坦納點Q與三角形鈍角頂點重合，如圖2（b）所示。

圖2　斯坦納點Q位置

定義2三角形斯坦納樹：對于平面中能夠組成三角形的三個點，分別連接該三角形斯坦納點與三個點，從而使三個點連通，連通后的結構稱為三角形斯坦納樹。

2　 CRATST算法

尋找最小斯坦納樹已被證明是一個NP難問題［17］，論文提出啟發式算法CRATST解決該問題。CRATST算法旨在用較少的中繼節點恢復分區連通性，同時獲得較好的網絡拓撲。該算法首先通過傳統方法恢復分區連通性，然后通過構建斯坦納樹減少中繼節點數量。具體分為初始部署，啟發式部署，斯坦納部署，檢查部署四個階段，逐步減少中繼節點數量實現分區的連通。

2.1初始部署

初始部署啟動后，根據給定的目標區域A計算A的幾何中心為O點。在每個分區Segi與網絡區域中心O的連線上，每隔距離R部署一個中繼節點，實現每個分區與區域中心O的連通。為了確保所有分區間能夠相互連通，在O位置部署中繼節點。

以Dist(Segi,O)表示分區Segi與中心O的距離，則每條路徑部署中繼節點的數量為：

2.2啟發式部署

為了減少初步部署的中繼節點數量，需對初始部署后的網絡進行優化。通過確定各個分區在順時針方向的排序，生成啟發式部署。排序步驟如下：

Step 1將區域中心O當作平面直角坐標系原點，比較每個分區與區域中心O橫縱坐標的大小，將所有分區劃分為以O為原點的4個象限。

Step 2求出所有分區與區域中心O連線的斜率，將各個象限內的分區根據斜率按從大到小順序排列。

Step 3將每個象限的分區排序按一四三二象限的順序串聯起來，即可得到分區相對于中心O在順時針方向的排序集合Turn。論文將排序中某個分區的前后兩個分區稱為該分區的相鄰分區。

分區確定排序后，啟動啟發式部署。啟發式部署偽代碼如表1所示。

表1　啟發式部署偽代碼

若Nij用來表示相鄰分區對Segi,Segj與中心位置O部署的中繼節點總數，則

2.3斯坦納部署

通過構造三角形斯坦納樹恢復相鄰分區對Segi,Segj與中心O三點的連通性，并與啟發式部署進行對比，進一步精減部署中繼節點的數量。若啟發式部署所需中繼數更少，則保留啟發式部署方案；如更多，則啟動斯坦納部署方案。斯坦納部署偽代碼如表2所示。

通過斯坦納部署，進一步優化了部署的中繼節點數量，但同時改變了啟發式形成的拓撲，可能造成一些分區不能與其他分區連通，故需要檢查部署以實現所有分區連通。

表2　斯坦納部署偽代碼

2.4檢查部署

根據斯坦納部署階段可知，未被選中且在啟發式部署階段提前終止部署的分區Segk可能會由于相鄰分區Segl的網絡拓撲已經改變，導致Seggk不能與其他分區連通，因此需在分區Segk與O之間補充部署中繼節點，從而實現所有分區之間的連通。

2.5算法復雜度分析

1C-SpiderWeb算法在恢復分區連通性的過程中，只進行了一次優化，而CRATST算法除了采用同樣的優化方法之外，進行了二次優化，以盡可能減少部署的中繼節點數量。故CRATST算法性能的改善建立在復雜度提高的基礎上。

3　算法案例

以圖1中網絡為案例，闡述CRATST恢復分區的連通性的具體操作步驟。抽象后的拓撲圖如圖3 （a）中所示，依原7個分區位置對應抽象為Segi(i=1,2,…,7)共計7個分區節點，彼此不連通。

圖3　CRATST算法案例

首先，每個分區Segi沿著中心O的方向部署中繼節點，如圖3（b）。

基于分區與O的距離確定集合D={Seg1,Seg6, Seg7,Seg3,Seg5,Seg2,Seg4}。經計算得到RN17和RN21、RN68和RN55、RN37和RN55分別能夠進行通信，因此分區Seg1、Seg6、Seg3的中繼節點將分別部署到RN17、RN68、RN37就停止，而分區Seg2,Seg4,Seg5,Seg7則保持初始部署階段形成的拓撲與O連通，如圖3（c）。

然后，基于3（a）重構斯坦納樹完成相鄰分區對與O的連通，如圖3（d），確定每個三角形斯坦納樹部署的中繼節點數量。基于Tij確定候選相鄰分區集合為Ctree ={Seg5,Seg6;Seg3,Seg5;Seg1,Seg2}，可判定分區對Seg5,Seg6與Seg1,Seg2應采用斯坦納樹方法部署中繼節點以重建連通；其它分區組依然保留啟發式部署方法實現與區域中心O的連通。

最后，由于Seg3的相鄰分區Seg5與中心O的連通拓撲已經改變，所以需在分區Seg3與中心O的路徑上繼續部署中繼節點，從而實現所有分區的連通。結果分區連通拓撲如圖3（e）。

4　仿真分析

通過與1C-SpiderWeb的對比實驗，論文將評測CRATST算法的效率，穩定性，功耗性能。其中，通過計算部署中繼節點數量評估算法效率。穩定性通過平均節點度來衡量。平均節點度等于恢復后的網絡拓撲中能夠直接通信的無線鏈路數量除以部署的中繼節點數量。平均節點度越高，表明恢復后的網絡穩定越好，節點能量消耗越可能趨于均衡。功耗性能可通過通信跳數來判斷。通信跳數為所有分區間相互通信一次所需的總跳數。對于雙向通信，各取值雙倍累加即可。

實驗采用Matlab軟件進行模擬。設定目標區域A為1 000 m×1 000 m的正方形區域，并且設定不同的分區數量Nseg和通信半徑R。其中，分區數量Nseg取值變化從4到7，通信半徑R取值從40 m到120 m每隔20取值一次，共計20種場景。分區位置在目標區域中隨機生成，仿真結果均為每種場景隨機生成30次網絡拓撲得到的均值。

4.1中繼節點數量

為了驗證CRATST算法的高效性，圖4統計了CRATST與1C-SpiderWeb算法在20種場景中網絡恢復連通所需中繼節點數量。

實驗結果如圖4所示，給定通信半徑R和分區數量Nseg，CRATST算法所需中繼節點數量小于1C-SpiderWeb算法。其原因在于，和1C-SpiderWeb算法僅在啟發式部署階段進行的單次優化相比，CRATST算法分別在啟發式部署和斯坦納部署階段，進行了二次優化。當給定分區數量Nseg，隨著通信半徑R的增加，相對于1C-SpiderWeb，在CRATST中由路徑長度減少帶來的高效優勢不再明顯，在圖中則體現為：隨R取值的增大，CRATST與1C-SpiderWeb所需中繼節點數量越來越接近。

4.2平均節點度

為了驗證CRATST算法的穩定性，圖5統計了CRATST與1C-SpiderWeb算法在20種場景中網絡恢復連通后的平均節點度。

圖5　平均節點度隨R和Nseg變化圖

實驗結果如圖5所示，給定通信半徑R和分區數量Nseg，1C-SpiderWeb算法以大量的中繼節點為代價恢復分區連通性，導致其平均節點度降低。因此，CRATST算法網絡拓撲的平均節點度要高于1CSpiderWeb算法。當分區數量Nseg一定，隨通信半徑R增加，2種算法的平均節點度隨之增加。這是因為通信半徑R增加，更多節點成為鄰居節點。但CRATST算法的平均節點度始終高于1C-SpiderWeb算法，說明CRATST算法形成網絡穩定性更好。

4.3通信跳數

為了驗證CRATST算法的低功耗性，圖6統計了CRATST與1C-SpiderWeb算法在20種場景中網絡恢復連通后的通信跳數。

圖6　通信跳數隨R和Nseg變化圖

實驗結果如圖6所示，給定通信半徑R和分區數量Nseg，所有分區間進行一次網絡通信，CRATST算法的跳數比1C-SpiderWeb算法要少，其原因在于CRATST算法通過兩次優化利用較少的中繼節點恢復分區連通性。而通信跳數的減少，說明CRATST算法相對于1C-SpiderWeb算法能夠有效減少能量消耗，延長網絡壽命。

5　結束語

論文提出基于三角形斯坦納樹的分區連通性恢復算法（CRATST）。算法在部署中繼節點的過程中，進行了啟發式和斯坦納部署的兩次優化，最大化地減少了中繼節點的數量，完成網絡連通性的恢復。

實驗從中繼節點數量、平均節點度和通信跳數三個方面入手，分別分析了算法效率、穩定性、功耗性能。通過與已有算法進行對比實驗，發現CRATST

在使用較少中繼節點的情況下，生成的網絡拓撲在效率、穩定性、功耗性方面具有更好的性能。

參考文獻：

［1］Younis M，Senturk I F，Akkaya K，et al. Topology Management Techniques for Tolerating Node Failures in Wireless Sensor Net?works：A Survey［J］. Computer Networks，2013，58（2）：254-283.

［2］Al-Turjman F M，Hassanein H S，Waleed M A，et al. Optimized Relay Placement for Wireless Sensor Networks Federation in Envi?ronmental Applications［J］. Wireless Communication and Mobile Computing，2011，11（12）：1677-1688.

［3］馬晨明，王萬良，洪榛.異構無線傳感器網絡中基于CDS樹的拓撲控制方法［J］.傳感技術學報，2014，27（6）：814-820.

［4］Lee S，Younis M. Optimized Relay Node Placement for Connect?ing Disjoint Wireless Sensor Networks［J］. Computer Networks，2012，56（12）：2788-2804.

［5］Senel F，Younis M. Relay Node Placement in Structurally Dam?aged Wireless Sensor Networks via Triangular Steiner Tree Ap? proximation［J］. Elsevier Computer Communications，2011，34 （16）：1932-1941.

［6］Senel F，Younis M. Optimized Relay Node Placement for Estab?lishing Connectivity in Sensor Networks［C］//Global Communica?tions Conference（GLOBECOM），Anaheim，CA，December 2012：512-517.

［7］Lee S，Younis M，Lee M. Connectivity Restoration in a Partitioned Wireless Sensor Network with Assured Fault Tolerance［J］. Ad Hoc Networks，2015，24（24）：1-19.

［8］陳洪生，石柯.基于四邊形斯坦納樹的無線傳感器網絡連通恢復［J］.計算機學報，2014，37（2）：457-468.

［9］楊洪，許力，章靜.無線傳感器網絡中容錯虛擬骨干網構造算法［J］.小型微型計算機系統，2014，35（12）：2612-2616.

［10］Joshi Y K，Younis M. Mobility-Based Internetworking of Disjoint Segments［C］//Communications（QBSC），2014 27th Biennial Sym?posium on IEEE，Kingston，ON，2014：193-197.

［11］Younis M，Lee S，Abbasi A A. A Localized Algorithm for Restor?ing Inter-Node Connectivity in Networks of Moveable Sensors［J］. IEEE Transactions on Computers，2010，59（12）：1669-1681.

［12］Lloyd E L，Xue G. Relay Node Placement in Wireless Sensor Net?works［J］.IEEETransactions on Computers，2007，56（1）：134-138.

［13］Senel F，Younis M，Akkaya K. A Robust Relay Node Placement Heuristic for Structurally Damaged Wireless Sensor Networks ［C］//Proceedings of the LCN’09，Zurich，Switzerland，Oct. 2009：633-640.

［14］Lee S，Younis M. Optimized Relay Placement to Federate Seg?ments in Wireless Sensor Networks［J］. IEEE Journal on Selected Area in Communications，Special Issue on Mission Critical Net?working，2010，28（5）：742-752.

［15］張會新，陳德沅，彭晴晴，等.一種改進的TDOA無線傳感器網絡節點定位算法［J］.傳感技術學報，2015，28（3）：412-415.

［16］Cheng X Z，Du D Z，Wang L S，et al. Relay Sensor Placement in Wireless Sensor Networks［J］. Wireless Networks，2008，14（3）：347-355.

［17］Lin G H，Xue G. Steiner Tree Problem with Minimum Mumber of Steiner Points and Bounded Edge-Length［J］. Information Process?ing Letters，1999，69（2）：53-57.

秦寧寧（1980-），女，江南大學副教授，研究方向為無線傳感器網絡覆蓋，ningning801108@163.com；

吳德恩（1988-），男，江南大學碩士研究生，研究方向為無線傳感器網絡連通性修復，1004995682@qq.com；

余穎華（1989-）女，江南大學碩士研究生，研究方向為無線傳感器網絡覆蓋，yuyinghuahn@163.com。

Connectivity Recovery Algorithm in Partition Based on Triangle Steiner Tree*

QIN Ningning1，2*，WU Deen1，YU Yinghua1
（1.School of Internet of Things Engineering，Jiangnan University，Wuxi Jiangsu 214122，China；2.Key Laboratory of Advanced Process Control for Light Industry Ministry of Education，Jiangnan University，Wuxi Jiangsu 214122，China）

Abstract：Due to the consumption of energy as well as the impact of other external factors，nodes in wireless sensor networks（WSN）can easily encounter the problem of large-scale failure，thus getting the networks divided into sever?al independent partitions which can’t effectively communicate with each other. In order to restore the network and reconstruct the communication links between the partitions，a triangle steiner tree based connectivity restoration al?gorithm is proposed. The algorithm first employs a traditional algorithm to achieve partition connectivity，and then by constructing triangle Steiner tree the number of deployed relay nodes can be reduced. Compared with some exist?ing algorithms，the topology of the network formed in this article can not only reduce the number of deployed relay nodes and make the partitions reconnected，but also is able to cut down the energy consumption of network commu?nication. The simulation results altogether indicate the proposed algorithm is more effective than traditional meth?ods in buildingthe network topology.

Key words：wireless sensor network；connectivity；triangle steiner tree；partition

doi：EEACC：6150P10.3969/j.issn.1004-1699.2016.03.020

收稿日期：2015-09-21修改日期：2015-10-27

中圖分類號：TP393

文獻標識碼：A

文章編號：1004-1699（2016）03-0423-06