秦寧寧，吳德恩，余穎華（.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫2422；2.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫2422）

?

基于三角形斯坦納樹(shù)的分區(qū)連通性恢復(fù)算法*

秦寧寧1，2*，吳德恩1，余穎華1
（1.江南大學(xué)物聯(lián)網(wǎng)工程學(xué)院，江蘇無(wú)錫214122；2.江南大學(xué)輕工過(guò)程先進(jìn)控制教育部重點(diǎn)實(shí)驗(yàn)室，江蘇無(wú)錫214122）

摘要：無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)由于自身能量的消耗，及外部因素影響會(huì)導(dǎo)致節(jié)點(diǎn)出現(xiàn)大規(guī)模的失效，從而把無(wú)線傳感器網(wǎng)絡(luò)分割成幾個(gè)獨(dú)立的不能相互通信的分區(qū)。為恢復(fù)網(wǎng)絡(luò)，重建分區(qū)之間的通信鏈路，提出基于三角形斯坦納樹(shù)連通恢復(fù)算法。該算法首先利用傳統(tǒng)算法實(shí)現(xiàn)分區(qū)連通，然后通過(guò)構(gòu)建三角形斯坦納樹(shù)以減少部署的中繼節(jié)點(diǎn)數(shù)量。與現(xiàn)有的一些算法相比，該方法形成的網(wǎng)絡(luò)拓?fù)洳粌H減少了部署中繼節(jié)點(diǎn)的數(shù)量，能夠使分區(qū)重新連通，而且能夠減少網(wǎng)絡(luò)通信的能量消耗。實(shí)驗(yàn)結(jié)果表明，所提方法相對(duì)于傳統(tǒng)算法在構(gòu)建網(wǎng)絡(luò)拓?fù)鋾r(shí)更加有效。

關(guān)鍵詞：無(wú)線傳感器網(wǎng)絡(luò)；連通性；三角形斯坦納樹(shù)；分區(qū)

項(xiàng)目來(lái)源：江蘇省“六大人才高峰”第十一批高層次人才項(xiàng)目（DZXX-026）；2014年國(guó)家公派高級(jí)研究學(xué)者及訪問(wèn)學(xué)者（含博士后）項(xiàng)目；國(guó)家自然科學(xué)基金項(xiàng)目（61304264）；江蘇高校優(yōu)勢(shì)學(xué)科建設(shè)工程項(xiàng)目；江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新資金前瞻性聯(lián)合研究項(xiàng)目（BY2014023-31）；中央高校基本科研業(yè)務(wù)費(fèi)專(zhuān)項(xiàng)資金項(xiàng)目（JUSRP51510）

無(wú)線傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)具有體積小、成本低等特點(diǎn)［1-3］，在提高網(wǎng)絡(luò)應(yīng)用靈活性的同時(shí)，也決定了節(jié)點(diǎn)不可能攜帶可供長(zhǎng)期使用的能量模塊。在惡劣的環(huán)境下，能量有限的節(jié)點(diǎn)很容易受自然環(huán)境或人為因素的影響而出現(xiàn)大規(guī)模的損壞［4-6］，造成網(wǎng)絡(luò)分割成獨(dú)立分區(qū)而不能相互通信，從而喪失了監(jiān)測(cè)能力。因此，恢復(fù)網(wǎng)絡(luò)的連通性成為一個(gè)至關(guān)重要的研究課題［7］。

在恢復(fù)受損網(wǎng)絡(luò)的連通性工作中，部署中繼節(jié)點(diǎn)無(wú)疑是一個(gè)快速有效的方法［8］。通常中繼節(jié)點(diǎn)擁有比普通節(jié)點(diǎn)更多的能量，更遠(yuǎn)的通信范圍［9］，以其作為各個(gè)分離分區(qū)之間的重建橋梁，可以解決分區(qū)之間的連通性問(wèn)題［10］。在中繼修復(fù)過(guò)程中，最關(guān)鍵的問(wèn)題是如何能部署更少的中繼節(jié)點(diǎn)同時(shí)確保相互獨(dú)立的分區(qū)能重新進(jìn)行通信［11］。

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

為克服調(diào)度中繼節(jié)點(diǎn)補(bǔ)位過(guò)程中，在復(fù)雜度、效率、數(shù)據(jù)傳輸延遲等多方面性能難于兼顧的問(wèn)題。論文提出了基于三角形斯坦納樹(shù)連通性恢復(fù)算法CRATST（Connectivity Recovery Algorithm based on Triangle Steiner Tree），通過(guò)引入斯坦納點(diǎn)，構(gòu)造三角形斯坦納樹(shù)，減少恢復(fù)分區(qū)連通性所需的中繼節(jié)點(diǎn)數(shù)量，降低分區(qū)間通信的距離與能量消耗，提高網(wǎng)絡(luò)的性能。

1　網(wǎng)絡(luò)描述

1.1網(wǎng)絡(luò)模型

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

不失一般性，設(shè)定網(wǎng)絡(luò)為靜態(tài)同構(gòu)網(wǎng)絡(luò)，即所有節(jié)點(diǎn)具有相同的感知半徑r和通信半徑R。部署的中繼節(jié)點(diǎn)與已有節(jié)點(diǎn)具有相同的感知半徑和通信半徑。節(jié)點(diǎn)可以利用已有的定位算法獲得自身位置信息［15］。

圖1　網(wǎng)絡(luò)受破壞后，形成獨(dú)立分區(qū)

1.2相關(guān)知識(shí)與定義

定義1三角形的斯坦納點(diǎn)：三角形內(nèi)到三頂點(diǎn)距離之和最小的點(diǎn)即為三角形的斯坦納點(diǎn)［16］。

對(duì)于給定網(wǎng)絡(luò)S，任意三個(gè)相鄰的節(jié)點(diǎn)Si,Sj,Sk構(gòu)成三角形△SiSjSk，且其中不包含其它節(jié)點(diǎn)。若△SiSjSk中存在斯坦納點(diǎn)Q，根據(jù)文獻(xiàn)［16］關(guān)于三角形斯坦納點(diǎn)的位置特征，結(jié)合△SiSjSk的內(nèi)角大小，Q的位置可基于如下2種情況進(jìn)行確定。

①∠SiSjSk,SjSiSk,SiSkSj<

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

則基于式（1），可確定斯坦納點(diǎn)Q的坐標(biāo)。

若△SiSjSk中存在某內(nèi)角∠SiSjSk≥，根據(jù)文獻(xiàn)［16］可知，其斯坦納點(diǎn)Q與三角形鈍角頂點(diǎn)重合，如圖2（b）所示。

圖2　斯坦納點(diǎn)Q位置

定義2三角形斯坦納樹(shù)：對(duì)于平面中能夠組成三角形的三個(gè)點(diǎn)，分別連接該三角形斯坦納點(diǎn)與三個(gè)點(diǎn)，從而使三個(gè)點(diǎn)連通，連通后的結(jié)構(gòu)稱(chēng)為三角形斯坦納樹(shù)。

2　 CRATST算法

尋找最小斯坦納樹(shù)已被證明是一個(gè)NP難問(wèn)題［17］，論文提出啟發(fā)式算法CRATST解決該問(wèn)題。CRATST算法旨在用較少的中繼節(jié)點(diǎn)恢復(fù)分區(qū)連通性，同時(shí)獲得較好的網(wǎng)絡(luò)拓?fù)洹Ｔ撍惴ㄊ紫韧ㄟ^(guò)傳統(tǒng)方法恢復(fù)分區(qū)連通性，然后通過(guò)構(gòu)建斯坦納樹(shù)減少中繼節(jié)點(diǎn)數(shù)量。具體分為初始部署，啟發(fā)式部署，斯坦納部署，檢查部署四個(gè)階段，逐步減少中繼節(jié)點(diǎn)數(shù)量實(shí)現(xiàn)分區(qū)的連通。

2.1初始部署

初始部署啟動(dòng)后，根據(jù)給定的目標(biāo)區(qū)域A計(jì)算A的幾何中心為O點(diǎn)。在每個(gè)分區(qū)Segi與網(wǎng)絡(luò)區(qū)域中心O的連線上，每隔距離R部署一個(gè)中繼節(jié)點(diǎn)，實(shí)現(xiàn)每個(gè)分區(qū)與區(qū)域中心O的連通。為了確保所有分區(qū)間能夠相互連通，在O位置部署中繼節(jié)點(diǎn)。

以Dist(Segi,O)表示分區(qū)Segi與中心O的距離，則每條路徑部署中繼節(jié)點(diǎn)的數(shù)量為：

2.2啟發(fā)式部署

為了減少初步部署的中繼節(jié)點(diǎn)數(shù)量，需對(duì)初始部署后的網(wǎng)絡(luò)進(jìn)行優(yōu)化。通過(guò)確定各個(gè)分區(qū)在順時(shí)針?lè)较虻呐判?，生成啟發(fā)式部署。排序步驟如下：

Step 1將區(qū)域中心O當(dāng)作平面直角坐標(biāo)系原點(diǎn)，比較每個(gè)分區(qū)與區(qū)域中心O橫縱坐標(biāo)的大小，將所有分區(qū)劃分為以O(shè)為原點(diǎn)的4個(gè)象限。

Step 2求出所有分區(qū)與區(qū)域中心O連線的斜率，將各個(gè)象限內(nèi)的分區(qū)根據(jù)斜率按從大到小順序排列。

Step 3將每個(gè)象限的分區(qū)排序按一四三二象限的順序串聯(lián)起來(lái)，即可得到分區(qū)相對(duì)于中心O在順時(shí)針?lè)较虻呐判蚣蟃urn。論文將排序中某個(gè)分區(qū)的前后兩個(gè)分區(qū)稱(chēng)為該分區(qū)的相鄰分區(qū)。

分區(qū)確定排序后，啟動(dòng)啟發(fā)式部署。啟發(fā)式部署偽代碼如表1所示。

表1　啟發(fā)式部署偽代碼

若Nij用來(lái)表示相鄰分區(qū)對(duì)Segi,Segj與中心位置O部署的中繼節(jié)點(diǎn)總數(shù)，則

2.3斯坦納部署

通過(guò)構(gòu)造三角形斯坦納樹(shù)恢復(fù)相鄰分區(qū)對(duì)Segi,Segj與中心O三點(diǎn)的連通性，并與啟發(fā)式部署進(jìn)行對(duì)比，進(jìn)一步精減部署中繼節(jié)點(diǎn)的數(shù)量。若啟發(fā)式部署所需中繼數(shù)更少，則保留啟發(fā)式部署方案；如更多，則啟動(dòng)斯坦納部署方案。斯坦納部署偽代碼如表2所示。

通過(guò)斯坦納部署，進(jìn)一步優(yōu)化了部署的中繼節(jié)點(diǎn)數(shù)量，但同時(shí)改變了啟發(fā)式形成的拓?fù)?，可能造成一些分區(qū)不能與其他分區(qū)連通，故需要檢查部署以實(shí)現(xiàn)所有分區(qū)連通。

表2　斯坦納部署偽代碼

2.4檢查部署

根據(jù)斯坦納部署階段可知，未被選中且在啟發(fā)式部署階段提前終止部署的分區(qū)Segk可能會(huì)由于相鄰分區(qū)Segl的網(wǎng)絡(luò)拓?fù)湟呀?jīng)改變，導(dǎo)致Seggk不能與其他分區(qū)連通，因此需在分區(qū)Segk與O之間補(bǔ)充部署中繼節(jié)點(diǎn)，從而實(shí)現(xiàn)所有分區(qū)之間的連通。

2.5算法復(fù)雜度分析

1C-SpiderWeb算法在恢復(fù)分區(qū)連通性的過(guò)程中，只進(jìn)行了一次優(yōu)化，而CRATST算法除了采用同樣的優(yōu)化方法之外，進(jìn)行了二次優(yōu)化，以盡可能減少部署的中繼節(jié)點(diǎn)數(shù)量。故CRATST算法性能的改善建立在復(fù)雜度提高的基礎(chǔ)上。

3　算法案例

以圖1中網(wǎng)絡(luò)為案例，闡述CRATST恢復(fù)分區(qū)的連通性的具體操作步驟。抽象后的拓?fù)鋱D如圖3 （a）中所示，依原7個(gè)分區(qū)位置對(duì)應(yīng)抽象為Segi(i=1,2,…,7)共計(jì)7個(gè)分區(qū)節(jié)點(diǎn)，彼此不連通。

圖3　CRATST算法案例

首先，每個(gè)分區(qū)Segi沿著中心O的方向部署中繼節(jié)點(diǎn)，如圖3（b）。

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

然后，基于3（a）重構(gòu)斯坦納樹(shù)完成相鄰分區(qū)對(duì)與O的連通，如圖3（d），確定每個(gè)三角形斯坦納樹(shù)部署的中繼節(jié)點(diǎn)數(shù)量?；赥ij確定候選相鄰分區(qū)集合為Ctree ={Seg5,Seg6;Seg3,Seg5;Seg1,Seg2}，可判定分區(qū)對(duì)Seg5,Seg6與Seg1,Seg2應(yīng)采用斯坦納樹(shù)方法部署中繼節(jié)點(diǎn)以重建連通；其它分區(qū)組依然保留啟發(fā)式部署方法實(shí)現(xiàn)與區(qū)域中心O的連通。

最后，由于Seg3的相鄰分區(qū)Seg5與中心O的連通拓?fù)湟呀?jīng)改變，所以需在分區(qū)Seg3與中心O的路徑上繼續(xù)部署中繼節(jié)點(diǎn)，從而實(shí)現(xiàn)所有分區(qū)的連通。結(jié)果分區(qū)連通拓?fù)淙鐖D3（e）。

4　仿真分析

通過(guò)與1C-SpiderWeb的對(duì)比實(shí)驗(yàn)，論文將評(píng)測(cè)CRATST算法的效率，穩(wěn)定性，功耗性能。其中，通過(guò)計(jì)算部署中繼節(jié)點(diǎn)數(shù)量評(píng)估算法效率。穩(wěn)定性通過(guò)平均節(jié)點(diǎn)度來(lái)衡量。平均節(jié)點(diǎn)度等于恢復(fù)后的網(wǎng)絡(luò)拓?fù)渲心軌蛑苯油ㄐ诺臒o(wú)線鏈路數(shù)量除以部署的中繼節(jié)點(diǎn)數(shù)量。平均節(jié)點(diǎn)度越高，表明恢復(fù)后的網(wǎng)絡(luò)穩(wěn)定越好，節(jié)點(diǎn)能量消耗越可能趨于均衡。功耗性能可通過(guò)通信跳數(shù)來(lái)判斷。通信跳數(shù)為所有分區(qū)間相互通信一次所需的總跳數(shù)。對(duì)于雙向通信，各取值雙倍累加即可。

實(shí)驗(yàn)采用Matlab軟件進(jìn)行模擬。設(shè)定目標(biāo)區(qū)域A為1 000 m×1 000 m的正方形區(qū)域，并且設(shè)定不同的分區(qū)數(shù)量Nseg和通信半徑R。其中，分區(qū)數(shù)量Nseg取值變化從4到7，通信半徑R取值從40 m到120 m每隔20取值一次，共計(jì)20種場(chǎng)景。分區(qū)位置在目標(biāo)區(qū)域中隨機(jī)生成，仿真結(jié)果均為每種場(chǎng)景隨機(jī)生成30次網(wǎng)絡(luò)拓?fù)涞玫降木怠?/p>

4.1中繼節(jié)點(diǎn)數(shù)量

為了驗(yàn)證CRATST算法的高效性，圖4統(tǒng)計(jì)了CRATST與1C-SpiderWeb算法在20種場(chǎng)景中網(wǎng)絡(luò)恢復(fù)連通所需中繼節(jié)點(diǎn)數(shù)量。

實(shí)驗(yàn)結(jié)果如圖4所示，給定通信半徑R和分區(qū)數(shù)量Nseg，CRATST算法所需中繼節(jié)點(diǎn)數(shù)量小于1C-SpiderWeb算法。其原因在于，和1C-SpiderWeb算法僅在啟發(fā)式部署階段進(jìn)行的單次優(yōu)化相比，CRATST算法分別在啟發(fā)式部署和斯坦納部署階段，進(jìn)行了二次優(yōu)化。當(dāng)給定分區(qū)數(shù)量Nseg，隨著通信半徑R的增加，相對(duì)于1C-SpiderWeb，在CRATST中由路徑長(zhǎng)度減少帶來(lái)的高效優(yōu)勢(shì)不再明顯，在圖中則體現(xiàn)為：隨R取值的增大，CRATST與1C-SpiderWeb所需中繼節(jié)點(diǎn)數(shù)量越來(lái)越接近。

4.2平均節(jié)點(diǎn)度

為了驗(yàn)證CRATST算法的穩(wěn)定性，圖5統(tǒng)計(jì)了CRATST與1C-SpiderWeb算法在20種場(chǎng)景中網(wǎng)絡(luò)恢復(fù)連通后的平均節(jié)點(diǎn)度。

圖5　平均節(jié)點(diǎn)度隨R和Nseg變化圖

實(shí)驗(yàn)結(jié)果如圖5所示，給定通信半徑R和分區(qū)數(shù)量Nseg，1C-SpiderWeb算法以大量的中繼節(jié)點(diǎn)為代價(jià)恢復(fù)分區(qū)連通性，導(dǎo)致其平均節(jié)點(diǎn)度降低。因此，CRATST算法網(wǎng)絡(luò)拓?fù)涞钠骄?jié)點(diǎn)度要高于1CSpiderWeb算法。當(dāng)分區(qū)數(shù)量Nseg一定，隨通信半徑R增加，2種算法的平均節(jié)點(diǎn)度隨之增加。這是因?yàn)橥ㄐ虐霃絉增加，更多節(jié)點(diǎn)成為鄰居節(jié)點(diǎn)。但CRATST算法的平均節(jié)點(diǎn)度始終高于1C-SpiderWeb算法，說(shuō)明CRATST算法形成網(wǎng)絡(luò)穩(wěn)定性更好。

4.3通信跳數(shù)

為了驗(yàn)證CRATST算法的低功耗性，圖6統(tǒng)計(jì)了CRATST與1C-SpiderWeb算法在20種場(chǎng)景中網(wǎng)絡(luò)恢復(fù)連通后的通信跳數(shù)。

圖6　通信跳數(shù)隨R和Nseg變化圖

實(shí)驗(yàn)結(jié)果如圖6所示，給定通信半徑R和分區(qū)數(shù)量Nseg，所有分區(qū)間進(jìn)行一次網(wǎng)絡(luò)通信，CRATST算法的跳數(shù)比1C-SpiderWeb算法要少，其原因在于CRATST算法通過(guò)兩次優(yōu)化利用較少的中繼節(jié)點(diǎn)恢復(fù)分區(qū)連通性。而通信跳數(shù)的減少，說(shuō)明CRATST算法相對(duì)于1C-SpiderWeb算法能夠有效減少能量消耗，延長(zhǎng)網(wǎng)絡(luò)壽命。

5　結(jié)束語(yǔ)

論文提出基于三角形斯坦納樹(shù)的分區(qū)連通性恢復(fù)算法（CRATST）。算法在部署中繼節(jié)點(diǎn)的過(guò)程中，進(jìn)行了啟發(fā)式和斯坦納部署的兩次優(yōu)化，最大化地減少了中繼節(jié)點(diǎn)的數(shù)量，完成網(wǎng)絡(luò)連通性的恢復(fù)。

實(shí)驗(yàn)從中繼節(jié)點(diǎn)數(shù)量、平均節(jié)點(diǎn)度和通信跳數(shù)三個(gè)方面入手，分別分析了算法效率、穩(wěn)定性、功耗性能。通過(guò)與已有算法進(jìn)行對(duì)比實(shí)驗(yàn)，發(fā)現(xiàn)CRATST

在使用較少中繼節(jié)點(diǎn)的情況下，生成的網(wǎng)絡(luò)拓?fù)湓谛?、穩(wěn)定性、功耗性方面具有更好的性能。

參考文獻(xiàn)：

［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］馬晨明，王萬(wàn)良，洪榛.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)中基于CDS樹(shù)的拓?fù)淇刂品椒ǎ跩］.傳感技術(shù)學(xué)報(bào)，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］陳洪生，石柯.基于四邊形斯坦納樹(shù)的無(wú)線傳感器網(wǎng)絡(luò)連通恢復(fù)［J］.計(jì)算機(jī)學(xué)報(bào)，2014，37（2）：457-468.

［9］楊洪，許力，章靜.無(wú)線傳感器網(wǎng)絡(luò)中容錯(cuò)虛擬骨干網(wǎng)構(gòu)造算法［J］.小型微型計(jì)算機(jī)系統(tǒng)，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］張會(huì)新，陳德沅，彭晴晴，等.一種改進(jìn)的TDOA無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)定位算法［J］.傳感技術(shù)學(xué)報(bào)，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-），女，江南大學(xué)副教授，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)覆蓋，ningning801108@163.com；

吳德恩（1988-），男，江南大學(xué)碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)連通性修復(fù)，1004995682@qq.com；

余穎華（1989-）女，江南大學(xué)碩士研究生，研究方向?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)覆蓋，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

中圖分類(lèi)號(hào)：TP393

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1004-1699（2016）03-0423-06