秦寧寧,吳德恩,余穎華(.江南大學物聯(lián)網(wǎng)工程學院,江蘇無錫2422;2.江南大學輕工過程先進控制教育部重點實驗室,江蘇無錫2422)
?
基于三角形斯坦納樹的分區(qū)連通性恢復算法*
秦寧寧1,2*,吳德恩1,余穎華1
(1.江南大學物聯(lián)網(wǎng)工程學院,江蘇無錫214122;2.江南大學輕工過程先進控制教育部重點實驗室,江蘇無錫214122)
摘要:無線傳感器網(wǎng)絡(luò)中的節(jié)點由于自身能量的消耗,及外部因素影響會導致節(jié)點出現(xiàn)大規(guī)模的失效,從而把無線傳感器網(wǎng)絡(luò)分割成幾個獨立的不能相互通信的分區(qū)。為恢復網(wǎng)絡(luò),重建分區(qū)之間的通信鏈路,提出基于三角形斯坦納樹連通恢復算法。該算法首先利用傳統(tǒng)算法實現(xiàn)分區(qū)連通,然后通過構(gòu)建三角形斯坦納樹以減少部署的中繼節(jié)點數(shù)量。與現(xiàn)有的一些算法相比,該方法形成的網(wǎng)絡(luò)拓撲不僅減少了部署中繼節(jié)點的數(shù)量,能夠使分區(qū)重新連通,而且能夠減少網(wǎng)絡(luò)通信的能量消耗。實驗結(jié)果表明,所提方法相對于傳統(tǒng)算法在構(gòu)建網(wǎng)絡(luò)拓撲時更加有效。
關(guān)鍵詞:無線傳感器網(wǎng)絡(luò);連通性;三角形斯坦納樹;分區(qū)
項目來源:江蘇省“六大人才高峰”第十一批高層次人才項目(DZXX-026);2014年國家公派高級研究學者及訪問學者(含博士后)項目;國家自然科學基金項目(61304264);江蘇高校優(yōu)勢學科建設(shè)工程項目;江蘇省產(chǎn)學研聯(lián)合創(chuàng)新資金前瞻性聯(lián)合研究項目(BY2014023-31);中央高校基本科研業(yè)務費專項資金項目(JUSRP51510)
無線傳感器網(wǎng)絡(luò)中的節(jié)點具有體積小、成本低等特點[1-3],在提高網(wǎng)絡(luò)應用靈活性的同時,也決定了節(jié)點不可能攜帶可供長期使用的能量模塊。在惡劣的環(huán)境下,能量有限的節(jié)點很容易受自然環(huán)境或人為因素的影響而出現(xiàn)大規(guī)模的損壞[4-6],造成網(wǎng)絡(luò)分割成獨立分區(qū)而不能相互通信,從而喪失了監(jiān)測能力。因此,恢復網(wǎng)絡(luò)的連通性成為一個至關(guān)重要的研究課題[7]。
在恢復受損網(wǎng)絡(luò)的連通性工作中,部署中繼節(jié)點無疑是一個快速有效的方法[8]。通常中繼節(jié)點擁有比普通節(jié)點更多的能量,更遠的通信范圍[9],以其作為各個分離分區(qū)之間的重建橋梁,可以解決分區(qū)之間的連通性問題[10]。在中繼修復過程中,最關(guān)鍵的問題是如何能部署更少的中繼節(jié)點同時確保相互獨立的分區(qū)能重新進行通信[11]。
為了以更少的中繼節(jié)點恢復分區(qū)的連通性,許多啟發(fā)式方法已經(jīng)被提出。文獻[7]提出通過重置失效節(jié)點的鄰居位置來恢復網(wǎng)絡(luò)連通,然而這種方法不能處理多節(jié)點同時失效情況,且不能處理部分區(qū)域內(nèi)節(jié)點不能移動的情況。文獻[12]中的MST_ 1TRNP(Minimum Spanning Trees Algorithm Based on a Single-Tiered Relay Node Placement)算法采用krus?kal或prim算法尋找最小生成樹,根據(jù)邊長與中繼節(jié)點通信半徑,沿著樹的邊部署中繼節(jié)點恢復連通,但該方法復雜度較高,且恢復后網(wǎng)絡(luò)的節(jié)點平均連通度較低。為了提高節(jié)點平均連通度,單連通蜘蛛網(wǎng)1C-SpiderWeb(1-Connected Spiderweb)算法[13]通過形成一個類似于蜘蛛網(wǎng)的網(wǎng)絡(luò)結(jié)構(gòu)完成中繼節(jié)點布置,雖然提高了節(jié)點平均連通度,但大量中繼節(jié)點的布置代價降低了網(wǎng)絡(luò)效率,增大了分區(qū)間數(shù)據(jù)傳輸延遲?;诰W(wǎng)格優(yōu)化的分布式中繼節(jié)點布置算法[14]CORP(Cell-based Optimized Relay node Placement al?gorithm)將網(wǎng)絡(luò)劃分為大小相等的網(wǎng)格單元,根據(jù)分區(qū)所在網(wǎng)格位置,由外向內(nèi)畫長方形找到最短路徑,布置額外節(jié)點重建各個分區(qū)連接。所形成的網(wǎng)絡(luò)拓撲能均衡網(wǎng)絡(luò)數(shù)據(jù)傳輸量,降低了分區(qū)間數(shù)據(jù)傳輸延遲,但復雜度較高,不適合在大規(guī)模網(wǎng)絡(luò)中使用。
為克服調(diào)度中繼節(jié)點補位過程中,在復雜度、效率、數(shù)據(jù)傳輸延遲等多方面性能難于兼顧的問題。論文提出了基于三角形斯坦納樹連通性恢復算法CRATST(Connectivity Recovery Algorithm based on Triangle Steiner Tree),通過引入斯坦納點,構(gòu)造三角形斯坦納樹,減少恢復分區(qū)連通性所需的中繼節(jié)點數(shù)量,降低分區(qū)間通信的距離與能量消耗,提高網(wǎng)絡(luò)的性能。
1.1網(wǎng)絡(luò)模型
在給定空間A內(nèi)部署的傳感器網(wǎng)絡(luò)S={Si| i=1,2,?,N}遭受到大規(guī)模的破壞后,可能會被分裂成若干無法直接通信的子區(qū)域。如圖1所示,灰色圓點表示失效節(jié)點,白色圓點表示正常工作節(jié)點,若將能正常工作節(jié)點形成的孤立網(wǎng)絡(luò)稱為分區(qū),則圖1中存在7個分區(qū),并以Segi代表第i個分區(qū),i=1,2,?,Nseg,其中Nseg為分區(qū)數(shù)量。顯然,分區(qū)內(nèi)的節(jié)點能夠相互進行通信,分區(qū)間不能通信。
不失一般性,設(shè)定網(wǎng)絡(luò)為靜態(tài)同構(gòu)網(wǎng)絡(luò),即所有節(jié)點具有相同的感知半徑r和通信半徑R。部署的中繼節(jié)點與已有節(jié)點具有相同的感知半徑和通信半徑。節(jié)點可以利用已有的定位算法獲得自身位置信息[15]。
圖1 網(wǎng)絡(luò)受破壞后,形成獨立分區(qū)
1.2相關(guān)知識與定義
定義1三角形的斯坦納點:三角形內(nèi)到三頂點距離之和最小的點即為三角形的斯坦納點[16]。
對于給定網(wǎng)絡(luò)S,任意三個相鄰的節(jié)點Si,Sj,Sk構(gòu)成三角形△SiSjSk,且其中不包含其它節(jié)點。若△SiSjSk中存在斯坦納點Q,根據(jù)文獻[16]關(guān)于三角形斯坦納點的位置特征,結(jié)合△SiSjSk的內(nèi)角大小,Q的位置可基于如下2種情況進行確定。
①∠SiSjSk,SjSiSk,SiSkSj<
若∠SiSjSk,SjSiSk,SiSkSj<,根據(jù)文獻[16]可知,點Q必在三角形內(nèi),且與△SiSjSk任意兩點連線的夾角均為,如圖2(a)所示,即式(1)成立。
則基于式(1),可確定斯坦納點Q的坐標。
若△SiSjSk中存在某內(nèi)角∠SiSjSk≥,根據(jù)文獻[16]可知,其斯坦納點Q與三角形鈍角頂點重合,如圖2(b)所示。
圖2 斯坦納點Q位置
定義2三角形斯坦納樹:對于平面中能夠組成三角形的三個點,分別連接該三角形斯坦納點與三個點,從而使三個點連通,連通后的結(jié)構(gòu)稱為三角形斯坦納樹。
尋找最小斯坦納樹已被證明是一個NP難問題[17],論文提出啟發(fā)式算法CRATST解決該問題。CRATST算法旨在用較少的中繼節(jié)點恢復分區(qū)連通性,同時獲得較好的網(wǎng)絡(luò)拓撲。該算法首先通過傳統(tǒng)方法恢復分區(qū)連通性,然后通過構(gòu)建斯坦納樹減少中繼節(jié)點數(shù)量。具體分為初始部署,啟發(fā)式部署,斯坦納部署,檢查部署四個階段,逐步減少中繼節(jié)點數(shù)量實現(xiàn)分區(qū)的連通。
2.1初始部署
初始部署啟動后,根據(jù)給定的目標區(qū)域A計算A的幾何中心為O點。在每個分區(qū)Segi與網(wǎng)絡(luò)區(qū)域中心O的連線上,每隔距離R部署一個中繼節(jié)點,實現(xiàn)每個分區(qū)與區(qū)域中心O的連通。為了確保所有分區(qū)間能夠相互連通,在O位置部署中繼節(jié)點。
以Dist(Segi,O)表示分區(qū)Segi與中心O的距離,則每條路徑部署中繼節(jié)點的數(shù)量為:
2.2啟發(fā)式部署
為了減少初步部署的中繼節(jié)點數(shù)量,需對初始部署后的網(wǎng)絡(luò)進行優(yōu)化。通過確定各個分區(qū)在順時針方向的排序,生成啟發(fā)式部署。排序步驟如下:
Step 1將區(qū)域中心O當作平面直角坐標系原點,比較每個分區(qū)與區(qū)域中心O橫縱坐標的大小,將所有分區(qū)劃分為以O(shè)為原點的4個象限。
Step 2求出所有分區(qū)與區(qū)域中心O連線的斜率,將各個象限內(nèi)的分區(qū)根據(jù)斜率按從大到小順序排列。
Step 3將每個象限的分區(qū)排序按一四三二象限的順序串聯(lián)起來,即可得到分區(qū)相對于中心O在順時針方向的排序集合Turn。論文將排序中某個分區(qū)的前后兩個分區(qū)稱為該分區(qū)的相鄰分區(qū)。
分區(qū)確定排序后,啟動啟發(fā)式部署。啟發(fā)式部署偽代碼如表1所示。
表1 啟發(fā)式部署偽代碼
若Nij用來表示相鄰分區(qū)對Segi,Segj與中心位置O部署的中繼節(jié)點總數(shù),則
2.3斯坦納部署
通過構(gòu)造三角形斯坦納樹恢復相鄰分區(qū)對Segi,Segj與中心O三點的連通性,并與啟發(fā)式部署進行對比,進一步精減部署中繼節(jié)點的數(shù)量。若啟發(fā)式部署所需中繼數(shù)更少,則保留啟發(fā)式部署方案;如更多,則啟動斯坦納部署方案。斯坦納部署偽代碼如表2所示。
通過斯坦納部署,進一步優(yōu)化了部署的中繼節(jié)點數(shù)量,但同時改變了啟發(fā)式形成的拓撲,可能造成一些分區(qū)不能與其他分區(qū)連通,故需要檢查部署以實現(xiàn)所有分區(qū)連通。
表2 斯坦納部署偽代碼
2.4檢查部署
根據(jù)斯坦納部署階段可知,未被選中且在啟發(fā)式部署階段提前終止部署的分區(qū)Segk可能會由于相鄰分區(qū)Segl的網(wǎng)絡(luò)拓撲已經(jīng)改變,導致Seggk不能與其他分區(qū)連通,因此需在分區(qū)Segk與O之間補充部署中繼節(jié)點,從而實現(xiàn)所有分區(qū)之間的連通。
2.5算法復雜度分析
1C-SpiderWeb算法在恢復分區(qū)連通性的過程中,只進行了一次優(yōu)化,而CRATST算法除了采用同樣的優(yōu)化方法之外,進行了二次優(yōu)化,以盡可能減少部署的中繼節(jié)點數(shù)量。故CRATST算法性能的改善建立在復雜度提高的基礎(chǔ)上。
以圖1中網(wǎng)絡(luò)為案例,闡述CRATST恢復分區(qū)的連通性的具體操作步驟。抽象后的拓撲圖如圖3 (a)中所示,依原7個分區(qū)位置對應抽象為Segi(i=1,2,…,7)共計7個分區(qū)節(jié)點,彼此不連通。
圖3 CRATST算法案例
首先,每個分區(qū)Segi沿著中心O的方向部署中繼節(jié)點,如圖3(b)。
基于分區(qū)與O的距離確定集合D={Seg1,Seg6, Seg7,Seg3,Seg5,Seg2,Seg4}。經(jīng)計算得到RN17和RN21、RN68和RN55、RN37和RN55分別能夠進行通信,因此分區(qū)Seg1、Seg6、Seg3的中繼節(jié)點將分別部署到RN17、RN68、RN37就停止,而分區(qū)Seg2,Seg4,Seg5,Seg7則保持初始部署階段形成的拓撲與O連通,如圖3(c)。
然后,基于3(a)重構(gòu)斯坦納樹完成相鄰分區(qū)對與O的連通,如圖3(d),確定每個三角形斯坦納樹部署的中繼節(jié)點數(shù)量?;赥ij確定候選相鄰分區(qū)集合為Ctree ={Seg5,Seg6;Seg3,Seg5;Seg1,Seg2},可判定分區(qū)對Seg5,Seg6與Seg1,Seg2應采用斯坦納樹方法部署中繼節(jié)點以重建連通;其它分區(qū)組依然保留啟發(fā)式部署方法實現(xiàn)與區(qū)域中心O的連通。
最后,由于Seg3的相鄰分區(qū)Seg5與中心O的連通拓撲已經(jīng)改變,所以需在分區(qū)Seg3與中心O的路徑上繼續(xù)部署中繼節(jié)點,從而實現(xiàn)所有分區(qū)的連通。結(jié)果分區(qū)連通拓撲如圖3(e)。
通過與1C-SpiderWeb的對比實驗,論文將評測CRATST算法的效率,穩(wěn)定性,功耗性能。其中,通過計算部署中繼節(jié)點數(shù)量評估算法效率。穩(wěn)定性通過平均節(jié)點度來衡量。平均節(jié)點度等于恢復后的網(wǎng)絡(luò)拓撲中能夠直接通信的無線鏈路數(shù)量除以部署的中繼節(jié)點數(shù)量。平均節(jié)點度越高,表明恢復后的網(wǎng)絡(luò)穩(wěn)定越好,節(jié)點能量消耗越可能趨于均衡。功耗性能可通過通信跳數(shù)來判斷。通信跳數(shù)為所有分區(qū)間相互通信一次所需的總跳數(shù)。對于雙向通信,各取值雙倍累加即可。
實驗采用Matlab軟件進行模擬。設(shè)定目標區(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取值一次,共計20種場景。分區(qū)位置在目標區(qū)域中隨機生成,仿真結(jié)果均為每種場景隨機生成30次網(wǎng)絡(luò)拓撲得到的均值。
4.1中繼節(jié)點數(shù)量
為了驗證CRATST算法的高效性,圖4統(tǒng)計了CRATST與1C-SpiderWeb算法在20種場景中網(wǎng)絡(luò)恢復連通所需中繼節(jié)點數(shù)量。
實驗結(jié)果如圖4所示,給定通信半徑R和分區(qū)數(shù)量Nseg,CRATST算法所需中繼節(jié)點數(shù)量小于1C-SpiderWeb算法。其原因在于,和1C-SpiderWeb算法僅在啟發(fā)式部署階段進行的單次優(yōu)化相比,CRATST算法分別在啟發(fā)式部署和斯坦納部署階段,進行了二次優(yōu)化。當給定分區(qū)數(shù)量Nseg,隨著通信半徑R的增加,相對于1C-SpiderWeb,在CRATST中由路徑長度減少帶來的高效優(yōu)勢不再明顯,在圖中則體現(xiàn)為:隨R取值的增大,CRATST與1C-SpiderWeb所需中繼節(jié)點數(shù)量越來越接近。
4.2平均節(jié)點度
為了驗證CRATST算法的穩(wěn)定性,圖5統(tǒng)計了CRATST與1C-SpiderWeb算法在20種場景中網(wǎng)絡(luò)恢復連通后的平均節(jié)點度。
圖5 平均節(jié)點度隨R和Nseg變化圖
實驗結(jié)果如圖5所示,給定通信半徑R和分區(qū)數(shù)量Nseg,1C-SpiderWeb算法以大量的中繼節(jié)點為代價恢復分區(qū)連通性,導致其平均節(jié)點度降低。因此,CRATST算法網(wǎng)絡(luò)拓撲的平均節(jié)點度要高于1CSpiderWeb算法。當分區(qū)數(shù)量Nseg一定,隨通信半徑R增加,2種算法的平均節(jié)點度隨之增加。這是因為通信半徑R增加,更多節(jié)點成為鄰居節(jié)點。但CRATST算法的平均節(jié)點度始終高于1C-SpiderWeb算法,說明CRATST算法形成網(wǎng)絡(luò)穩(wěn)定性更好。
4.3通信跳數(shù)
為了驗證CRATST算法的低功耗性,圖6統(tǒng)計了CRATST與1C-SpiderWeb算法在20種場景中網(wǎng)絡(luò)恢復連通后的通信跳數(shù)。
圖6 通信跳數(shù)隨R和Nseg變化圖
實驗結(jié)果如圖6所示,給定通信半徑R和分區(qū)數(shù)量Nseg,所有分區(qū)間進行一次網(wǎng)絡(luò)通信,CRATST算法的跳數(shù)比1C-SpiderWeb算法要少,其原因在于CRATST算法通過兩次優(yōu)化利用較少的中繼節(jié)點恢復分區(qū)連通性。而通信跳數(shù)的減少,說明CRATST算法相對于1C-SpiderWeb算法能夠有效減少能量消耗,延長網(wǎng)絡(luò)壽命。
論文提出基于三角形斯坦納樹的分區(qū)連通性恢復算法(CRATST)。算法在部署中繼節(jié)點的過程中,進行了啟發(fā)式和斯坦納部署的兩次優(yōu)化,最大化地減少了中繼節(jié)點的數(shù)量,完成網(wǎng)絡(luò)連通性的恢復。
實驗從中繼節(jié)點數(shù)量、平均節(jié)點度和通信跳數(shù)三個方面入手,分別分析了算法效率、穩(wěn)定性、功耗性能。通過與已有算法進行對比實驗,發(fā)現(xiàn)CRATST
在使用較少中繼節(jié)點的情況下,生成的網(wǎng)絡(luò)拓撲在效率、穩(wě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]馬晨明,王萬良,洪榛.異構(gòu)無線傳感器網(wǎng)絡(luò)中基于CDS樹的拓撲控制方法[J].傳感技術(shù)學報,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]陳洪生,石柯.基于四邊形斯坦納樹的無線傳感器網(wǎng)絡(luò)連通恢復[J].計算機學報,2014,37(2):457-468.
[9]楊洪,許力,章靜.無線傳感器網(wǎng)絡(luò)中容錯虛擬骨干網(wǎng)構(gòu)造算法[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]張會新,陳德沅,彭晴晴,等.一種改進的TDOA無線傳感器網(wǎng)絡(luò)節(jié)點定位算法[J].傳感技術(shù)學報,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-),女,江南大學副教授,研究方向為無線傳感器網(wǎng)絡(luò)覆蓋,ningning801108@163.com;
吳德恩(1988-),男,江南大學碩士研究生,研究方向為無線傳感器網(wǎng)絡(luò)連通性修復,1004995682@qq.com;
余穎華(1989-)女,江南大學碩士研究生,研究方向為無線傳感器網(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
中圖分類號:TP393
文獻標識碼:A
文章編號:1004-1699(2016)03-0423-06