一種無線傳感器網絡可靠拓撲的生成算法*

和 鵬，畢紅軍

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

0 引 言

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

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

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

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

1 可靠拓撲的生成算法

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

可靠拓撲生成算法描述如下:首先構建一個1 邊連通拓撲D1(G)，它是G 的一個子圖，然后把所有屬于D1(G)的邊從G 中刪除。這樣做可能會使G 不連通并且由2 個或更多連通的分支組成。接下來，為每一個連通的分支構建一個對應的1 邊連通拓撲。然后把新找到的邊添加到D1(G)中形成2 邊連通拓撲D1(G)。上述算法是一個通用算法，它可以為不同支撐結構構建一個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是圖)的一個分支連通支撐子圖所有的邊。對于正整數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 邊連通的，定理得證。

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

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

2 仿真與性能分析

2.1 仿真環境

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

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

2.2 性能分析

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

首先，設定數據源節點產生數據包的概率為10%，20%，30%，40%，50%，鏈路失敗的概率設定為10%。不同拓撲的平均數據包傳輸率如圖1 所示。

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

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

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

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

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

實驗發現，數據包生成概率比鏈路失效概率對拓撲性能的影響更大，這是因為當最優路由連接失敗時，這些拓撲可以提供到匯聚節點的替代路由。

3 結 論

本文提出了一種無線傳感器網絡可靠拓撲生成算法，該算法能夠設計可靠的2 邊連通路由拓撲，為無線傳感器網提供替代路由。此外，分析了不同拓撲的可靠性和在連通失效時的鏈路質量。仿真結果顯示:基于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.