一種無線傳感器網(wǎng)絡(luò)可靠拓撲的生成算法*

和 鵬，畢紅軍

(北京交通大學 通信與信息系統(tǒng)北京市重點實驗室，北京100044)

0 引 言

無線傳感器網(wǎng)絡(luò)(WSNs)是由部署在監(jiān)測區(qū)域內(nèi)大量的、簡單的傳感器節(jié)點組成，通過無線通信方式形成的一個多跳的自組織的網(wǎng)絡(luò)系統(tǒng)，其被廣泛應用于醫(yī)療衛(wèi)生、環(huán)境保護、軍事偵察等領(lǐng)域。這些應用都需要節(jié)點將采集到的數(shù)據(jù)信息傳送到匯聚節(jié)點，匯聚節(jié)點將數(shù)據(jù)融合后再進行合適的操作，然而，無線通信信道容易受到干擾和噪聲的影響，為確保數(shù)據(jù)信息傳送到匯聚節(jié)點，可靠性是一個很重要的問題。

現(xiàn)在已有許多關(guān)于拓撲生成算法的研究，這些研究在優(yōu)化節(jié)點度和路徑長度［1，2］，端到端延遲和數(shù)據(jù)包丟失［3］，能量消耗［4～6］等方面做了很多工作。例如:文獻［7］提出，當θ≥π 時，一個2π/θ 邊連通拓撲，被稱作無線傳感器網(wǎng)絡(luò)的物理拓撲。在文獻［8］中，基于最小生成樹的k 邊連通拓撲，被稱為LTRT。然而，以上研究都沒有在鏈路連接失敗時提供替代路由。

無線傳感器網(wǎng)絡(luò)可以描述成一個在二維歐幾里得空間中，由N 個節(jié)點組成的集合V。假定所有節(jié)點的傳輸距離為R，當且僅當兩個節(jié)點的歐幾里得距離小于等于R 時才能相互通信，這種相互通信的能力用相應節(jié)點之間的邊來描述。由此，圖G=(V，E)是網(wǎng)絡(luò)的物理拓撲，其中，G 為一個UDG 圖。由于網(wǎng)絡(luò)中的節(jié)點處于不斷變化的環(huán)境中，節(jié)點的狀態(tài)也在相應地發(fā)生變化，加之無線通信信道的不穩(wěn)定性，因此，G 也在不斷地調(diào)整變化。拓撲生成問題就是定義給定物理拓撲的子圖，隨之數(shù)據(jù)包路由就會形成。因此，本文將這種物理拓撲的子圖稱為路由拓撲。

本文對路由拓撲的可靠性問題進行研究，采用構(gòu)建可靠的網(wǎng)絡(luò)拓撲，提供替代路由傳遞重要信息的方法來提高可靠性。首先給出一個可以用于任何支撐結(jié)構(gòu)的k 邊連通拓撲結(jié)構(gòu)，并為此提出一個通用的算法。根據(jù)研究需要，考慮從最小生成樹(MST)、最短路徑樹(SPT)、度受限的最短路徑樹(DCSPT)和Gabriel圖(GG)等基本支撐拓撲構(gòu)建k邊連通拓撲。仿真實驗對不同拓撲的可靠性進行了探究。

1 可靠拓撲的生成算法

對于圖G=(V，E)，若G 的頂點數(shù)大于1 且對任意少于k 條邊的集合F?E，G-F 均是連通的，則稱G 是k 邊連通的，在G 中的任何兩個節(jié)點之間都有k 條不同的路連接。給定一個k 邊連通的物理拓撲G，構(gòu)建一個k 邊連通路由拓撲的問題就是找出一個G 的連通子圖Dk(G)，在Dk(G)中任意兩個節(jié)點之間都會有k 條分離式替代路徑。本文在構(gòu)建k 邊連通拓撲時，選取k=2，也就是在給定的物理拓撲中找出一個2 邊連通路由拓撲。

可靠拓撲生成算法描述如下:首先構(gòu)建一個1 邊連通拓撲D1(G)，它是G 的一個子圖，然后把所有屬于D1(G)的邊從G 中刪除。這樣做可能會使G 不連通并且由2 個或更多連通的分支組成。接下來，為每一個連通的分支構(gòu)建一個對應的1 邊連通拓撲。然后把新找到的邊添加到D1(G)中形成2 邊連通拓撲D1(G)。上述算法是一個通用算法，它可以為不同支撐結(jié)構(gòu)構(gòu)建一個k 邊連通拓撲。

算法1 k 邊連通拓撲Dk(G)

E1是G 的一個分支連通支撐子圖的邊

D1(G)←E

for i←1 to k-1 do

將D1(G)的邊刪除，得到連通分支Di1(G)，Di2(G)，…，Dil(G)

for j←1 to l do

生成分支連通支撐子圖Dil(G)

end for

合并Di1(G)，Di2(G)，…，Dil(G)以得到Dk(G)

end for

Dk(G)的k 連通特性在定理1 中得到了證明。

定理1 令E1是圖G=(V，E)的一個分支連通支撐子圖所有的邊。任意i≥2，令Ei是圖)的一個分支連通支撐子圖所有的邊。對于正整數(shù)i，圖Di(G)=(V，，則對于k≥1，如果G 是k 邊連通的，Dk(G)也是k邊連通的。

證明:用歸納法來證明，對于所有1≤l≤k，Dl(G)是l邊連通的。注意到D1(G)是G 的一個連通支撐子圖，也因此是1 邊連通的。再考慮2≤l≤k，假定Dl-1(G)是(l-1)邊連通的。對于和Dl(G)=(V，)就是Dl-1(G)簡單地加上邊El。

假定Dl(G)不是l 邊連通的，令{e1，…，el-1}是Dl(G)的一個割邊，割邊將頂點集合A 從頂點集合B 中分離出來，此處V=A∪B。因為Dl-1(G)是(l-1)邊連通的，所以，{e1，…，el-1}的每條邊必須是Dl-1(G)的一條邊。又由于G是l 邊連通的，所以，在中至少有一條邊連接A 和B。亦即A 和B 中各有一個頂點在中是連通的，而在(V，E1)中不連通，這與(V，E1)是的分支連通支撐子圖相矛盾。因此，可以得出Dl(G)是l 邊連通的，定理得證。

依據(jù)算法1，可以定義如下一系列的路由拓撲:首先利用MST 構(gòu)建子圖D1(G)，刪除D1(G)的邊，再次在子圖中利用MST 便可得到MST2。SPT2，DCSPT2 和Gabriel2 都是以同樣的方式來構(gòu)建。此外，Gabriel 可以和其他拓撲相結(jié)合，DCSPT-Gabriel(DCGB)拓撲也是G 的子圖，它首先根據(jù)DCSPT 構(gòu)建子圖，然后利用Gabriel 圖在剩余分支上構(gòu)建DCSPT-Gabriel。MST-Gabriel(MSGB)與DCGB 的構(gòu)建方式相同。

為了評估不同路由拓撲的性能，本文利用TDMA 鏈路調(diào)度。在TDMA 調(diào)度中，無沖突協(xié)議通過在鏈路中設(shè)置時隙來共享可利用帶寬并控制數(shù)據(jù)包傳輸。為達到這個目的，采用集中控制模式，在該模式下匯聚節(jié)點從節(jié)點處收集信息來計算和傳播調(diào)度長度。假設(shè)時隙的長度足夠包含一個從接收器發(fā)來的ACK。當一個傳感器節(jié)點傳輸?shù)男畔]有得到確認，它就會檢測到一個下行鏈路。因此，失效的鏈路會被本地檢測到，并且包路由也由本地決定。因為擁有2 連通拓撲，表示至少有2 條不同的鏈路以保證數(shù)據(jù)包路由到匯聚節(jié)點。當下行鏈路存在時，就需要交替利用2 條鏈路:一條是最好的鏈路，另一條可能是次好的鏈路。傳感器在每個安排的時隙里嘗試連接最優(yōu)的鏈路，如果嘗試失敗，傳感器在接下來的階段嘗試連接第二條鏈路。這個過程會持續(xù)下去，直到數(shù)據(jù)包通過1 條鏈路成功傳送或者達到重試次數(shù)的限制(在仿真中設(shè)定為7 次)。當達到重試次數(shù)限制時，數(shù)據(jù)包就會被丟棄。

2 仿真與性能分析

2.1 仿真環(huán)境

使用Matlab 仿真來評估路由拓撲的性能。重點討論在存在鏈路失效的情況下，不同拓撲的路徑質(zhì)量和提供替代路徑的能力。實驗中，將N 個傳感器節(jié)點均勻分布在100 m×100 m 的矩形區(qū)域。每個節(jié)點的傳輸范圍是25 m，節(jié)點在彼此的傳輸范圍內(nèi)時便可以相互通信，并由此產(chǎn)生底層物理拓撲，仿真只利用2 連通的物理拓撲。下面的每個結(jié)果都是1 000 次實驗的平均值，并給定95%的置信區(qū)間。

本文考慮在動態(tài)環(huán)境下進行仿真，允許每種拓撲自由選取他們最佳的匯聚節(jié)點，并觀察其相應的行為。

2.2 性能分析

本文主要探究數(shù)據(jù)包傳輸率。由于本文所分析的拓撲是2 邊連通的，并且網(wǎng)絡(luò)中的任何一個傳感器都能被選為匯聚節(jié)點。因此，在這個動態(tài)仿真環(huán)境中，選擇擁有最小調(diào)度長度的傳感器作為匯聚節(jié)點。為保證比較的一致性，每種拓撲的仿真運行時間和產(chǎn)生數(shù)據(jù)包的數(shù)量都相同。

首先，設(shè)定數(shù)據(jù)源節(jié)點產(chǎn)生數(shù)據(jù)包的概率為10%，20%，30%，40%，50%，鏈路失敗的概率設(shè)定為10%。不同拓撲的平均數(shù)據(jù)包傳輸率如圖1 所示。

圖1 不同數(shù)據(jù)包生成概率下平均數(shù)據(jù)包傳輸率Fig 1 Average data packet delivery ratio with different data packet generation probability

DCSPT2 和SPT2 的數(shù)據(jù)包傳輸率低于其他路由拓撲，這是由于盡管它們有最短路徑，但卻有更高的平均路徑長度。造成這種結(jié)果的原因是提供最佳調(diào)度的匯聚節(jié)點是相對于圖的邊來說的，這為并行傳輸提供了最大的機會，并且有最少的沖突。相比之下，Gabriel 和MST 匯聚節(jié)點的位置能夠提供更短的路徑長度。更長的路徑更容易因為連接失敗而失效，因此，數(shù)據(jù)包在仿真時傳輸率更低。基于Gabriel的拓撲有更多集中放置的匯聚節(jié)點和最短的路徑長度，可以更可靠地傳輸數(shù)據(jù)包。

設(shè)定數(shù)據(jù)包生成概率為1%，而鏈路失效概率設(shè)定為5%，10%，15%，20%，25%。不同鏈路失效概率下平均數(shù)據(jù)包傳輸率如圖2 所示。

圖2 不同鏈路失效概率下平均數(shù)據(jù)包傳輸率Fig 2 Average data packet delivery ratio with different link failure probability

正如預期的那樣，DCSPT2 和SPT2 的數(shù)據(jù)包傳輸率由于匯聚節(jié)點位置問題受到失效鏈路的影響最大，其他拓撲的性能都很穩(wěn)定，基于Gabriel 的混合方式DCGB，MSGB 性能最好。

實驗發(fā)現(xiàn)，數(shù)據(jù)包生成概率比鏈路失效概率對拓撲性能的影響更大，這是因為當最優(yōu)路由連接失敗時，這些拓撲可以提供到匯聚節(jié)點的替代路由。

3 結(jié) 論

本文提出了一種無線傳感器網(wǎng)絡(luò)可靠拓撲生成算法，該算法能夠設(shè)計可靠的2 邊連通路由拓撲，為無線傳感器網(wǎng)提供替代路由。此外，分析了不同拓撲的可靠性和在連通失效時的鏈路質(zhì)量。仿真結(jié)果顯示:基于Gabriel 圖的拓撲在可靠性和路徑冗余之間給出了最好的折中方案。

［1］ Ghosh A，Incel ? D，Kumar V S，et al.Multichannel scheduling and spanning trees:Throughput-delay trade-off for fast data collection in sensor networks［J］.IEEE/ACM Transactions on Networking(TON)，2011，19(6):1731-1744.

［2］ Gelal E，Jakllari G，Krishnamurthy S V，et al.Topology control to simultaneously achieve near-optimal node degree and low path stretch in Ad Hoc networks［C］∥2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks，SECON’06，IEEE，2006:431-439.

［3］ Zinonos Z，Vassiliou V，Ioannou C，et al.Dynamic topology control for WSNs in critical environments［C］∥2011 4th IFIP International Conference on New Technologies，Mobility and Security(NTMS)，IEEE，2011:1-5.

［4］ Staniec K，Debita G.Evaluation of topological planarity and reliability for interference reduction in radio sensor networks［J］.EURASIP Journal on Wireless Communications and Networking，2012(1):1-7.

［5］ Qureshi H K，Rizvi S，Saleem M，et al.Poly:A reliable and energy efficient topology control protocol for wireless sensor networks［J］.Computer Communications，2011，34(10):1235-1242.

［6］ Karim L，El Salti T，Nasser N，et al.The significant impact of a set of topologies on wireless sensor networks［J］.EURASIP Journal on Wireless Communications and Networking，2012(1):1-13.

［7］ Poduri S，Pattem S，Krishnamachari B，et al.Using local geometry for tunable topology control in sensor networks［C］∥IEEE Trans on Mobile Comput(TMC)，2009.

［8］ Miyao K，Nakayama H，Ansari N，et al.LTRT:An efficient and reliable topology control algorithm for Ad-Hoc networks［J］.IEEE Transactions on Wireless Communications，2009，8(12):6050-6058.