和 鵬，畢紅軍

(北京交通大學(xué) 通信與信息系統(tǒng)北京市重點(diǎn)實(shí)驗(yàn)室，北京100044)

0 引 言

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

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

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

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

1 可靠拓?fù)涞纳伤惴?/h2>

對(duì)于圖G=(V，E)，若G 的頂點(diǎn)數(shù)大于1 且對(duì)任意少于k 條邊的集合F?E，G-F 均是連通的，則稱(chēng)G 是k 邊連通的，在G 中的任何兩個(gè)節(jié)點(diǎn)之間都有k 條不同的路連接。給定一個(gè)k 邊連通的物理拓?fù)銰，構(gòu)建一個(gè)k 邊連通路由拓?fù)涞膯?wèn)題就是找出一個(gè)G 的連通子圖Dk(G)，在Dk(G)中任意兩個(gè)節(jié)點(diǎn)之間都會(huì)有k 條分離式替代路徑。本文在構(gòu)建k 邊連通拓?fù)鋾r(shí)，選取k=2，也就是在給定的物理拓?fù)渲姓页鲆粋€(gè)2 邊連通路由拓?fù)洹?/p>

可靠拓?fù)渖伤惴枋鋈缦?首先構(gòu)建一個(gè)1 邊連通拓?fù)銬1(G)，它是G 的一個(gè)子圖，然后把所有屬于D1(G)的邊從G 中刪除。這樣做可能會(huì)使G 不連通并且由2 個(gè)或更多連通的分支組成。接下來(lái)，為每一個(gè)連通的分支構(gòu)建一個(gè)對(duì)應(yīng)的1 邊連通拓?fù)?。然后把新找到的邊添加到D1(G)中形成2 邊連通拓?fù)銬1(G)。上述算法是一個(gè)通用算法，它可以為不同支撐結(jié)構(gòu)構(gòu)建一個(gè)k 邊連通拓?fù)洹?/p>

算法1 k 邊連通拓?fù)銬k(G)

E1是G 的一個(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)的一個(gè)分支連通支撐子圖所有的邊。任意i≥2，令Ei是圖)的一個(gè)分支連通支撐子圖所有的邊。對(duì)于正整數(shù)i，圖Di(G)=(V，，則對(duì)于k≥1，如果G 是k 邊連通的，Dk(G)也是k邊連通的。

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

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

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

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

2 仿真與性能分析

2.1 仿真環(huán)境

使用Matlab 仿真來(lái)評(píng)估路由拓?fù)涞男阅?。重點(diǎn)討論在存在鏈路失效的情況下，不同拓?fù)涞穆窂劫|(zhì)量和提供替代路徑的能力。實(shí)驗(yàn)中，將N 個(gè)傳感器節(jié)點(diǎn)均勻分布在100 m×100 m 的矩形區(qū)域。每個(gè)節(jié)點(diǎn)的傳輸范圍是25 m，節(jié)點(diǎn)在彼此的傳輸范圍內(nèi)時(shí)便可以相互通信，并由此產(chǎn)生底層物理拓?fù)?，仿真只利? 連通的物理拓?fù)洹Ｏ旅娴拿總€(gè)結(jié)果都是1 000 次實(shí)驗(yàn)的平均值，并給定95%的置信區(qū)間。

本文考慮在動(dòng)態(tài)環(huán)境下進(jìn)行仿真，允許每種拓?fù)渥杂蛇x取他們最佳的匯聚節(jié)點(diǎn)，并觀察其相應(yīng)的行為。

2.2 性能分析

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

首先，設(shè)定數(shù)據(jù)源節(jié)點(diǎn)產(chǎn)生數(shù)據(jù)包的概率為10%，20%，30%，40%，50%，鏈路失敗的概率設(shè)定為10%。不同拓?fù)涞钠骄鶖?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ù)包傳輸率低于其他路由拓?fù)?，這是由于盡管它們有最短路徑，但卻有更高的平均路徑長(zhǎng)度。造成這種結(jié)果的原因是提供最佳調(diào)度的匯聚節(jié)點(diǎn)是相對(duì)于圖的邊來(lái)說(shuō)的，這為并行傳輸提供了最大的機(jī)會(huì)，并且有最少的沖突。相比之下，Gabriel 和MST 匯聚節(jié)點(diǎn)的位置能夠提供更短的路徑長(zhǎng)度。更長(zhǎng)的路徑更容易因?yàn)檫B接失敗而失效，因此，數(shù)據(jù)包在仿真時(shí)傳輸率更低?；贕abriel的拓?fù)溆懈嗉蟹胖玫膮R聚節(jié)點(diǎn)和最短的路徑長(zhǎng)度，可以更可靠地傳輸數(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

正如預(yù)期的那樣，DCSPT2 和SPT2 的數(shù)據(jù)包傳輸率由于匯聚節(jié)點(diǎn)位置問(wèn)題受到失效鏈路的影響最大，其他拓?fù)涞男阅芏己芊€(wěn)定，基于Gabriel 的混合方式DCGB，MSGB 性能最好。

實(shí)驗(yàn)發(fā)現(xiàn)，數(shù)據(jù)包生成概率比鏈路失效概率對(duì)拓?fù)湫阅艿挠绊懜螅@是因?yàn)楫?dāng)最優(yōu)路由連接失敗時(shí)，這些拓?fù)淇梢蕴峁┑絽R聚節(jié)點(diǎn)的替代路由。

3 結(jié) 論

本文提出了一種無(wú)線傳感器網(wǎng)絡(luò)可靠拓?fù)渖伤惴?，該算法能夠設(shè)計(jì)可靠的2 邊連通路由拓?fù)洌瑸闊o(wú)線傳感器網(wǎng)提供替代路由。此外，分析了不同拓?fù)涞目煽啃院驮谶B通失效時(shí)的鏈路質(zhì)量。仿真結(jié)果顯示:基于Gabriel 圖的拓?fù)湓诳煽啃院吐窂饺哂嘀g給出了最好的折中方案。

［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.