無(wú)線傳感器網(wǎng)絡(luò)中分布式廣播算法研究.pdf

1、廣播是無(wú)線傳感器網(wǎng)絡(luò)中的基本問(wèn)題之一，它的效率直接決定了許多高層應(yīng)用和協(xié)議（如路由發(fā)現(xiàn)協(xié)議）的性能。根據(jù)所要廣播的消息個(gè)數(shù)不同，可以將廣播問(wèn)題劃分為單消息廣播和多消息廣播。在無(wú)線傳感器網(wǎng)絡(luò)中，無(wú)線通信往往受到干擾的影響，因此干擾建模對(duì)設(shè)計(jì)高效的網(wǎng)絡(luò)協(xié)議是非常重要的。近年來(lái)，物理干擾模型得到了廣泛應(yīng)用。在物理干擾模型中，干擾隨著距離的增加而減小并具有全局累加性特征，符合無(wú)線傳感器網(wǎng)絡(luò)的實(shí)際情況。現(xiàn)實(shí)中的無(wú)線傳感器網(wǎng)絡(luò)往往是一個(gè)分布式系統(tǒng)，

2、因而設(shè)計(jì)高效的分布式廣播算法更加具有現(xiàn)實(shí)意義。以往同步通訊模型下的分布式確定性單消息廣播算法為了從邏輯上將整個(gè)網(wǎng)絡(luò)進(jìn)行網(wǎng)格劃分，需要每個(gè)節(jié)點(diǎn)知道自己的坐標(biāo)信息。這將產(chǎn)生如下兩個(gè)問(wèn)題，第一，算法執(zhí)行的正確性和精確性在很大程度上取決于網(wǎng)絡(luò)中節(jié)點(diǎn)位置的定位精度；第二，為部分或全部節(jié)點(diǎn)配備GPS（Global Position System）設(shè)備將會(huì)帶來(lái)高成本和高能耗。此外，以往異步通訊模型下的分布式多消息廣播算法采用的是基于圖的干擾模型而不是

3、更加符合實(shí)際的物理干擾模型。鑒于以上原因，本文研究基于物理干擾模型的無(wú)坐標(biāo)依賴的分布式廣播算法的設(shè)計(jì)，主要內(nèi)容如下。
　　(1)在同步通訊模型下，設(shè)計(jì)了兩個(gè)基于標(biāo)準(zhǔn)物理干擾模型的分布式確定性單消息廣播算法。第一個(gè)廣播算法（the Time Efficient Global Broadcast，TEGB）首先從每一層節(jié)點(diǎn)中選取一個(gè)極大獨(dú)立集，接著將該極大獨(dú)立集劃分為若干子集以實(shí)現(xiàn)廣播消息最大程度的并發(fā)傳輸。理論分析表明，TEGB的時(shí)

4、間復(fù)雜度為O(Dlogn)，這里n表示節(jié)點(diǎn)總數(shù)，D為網(wǎng)絡(luò)的直徑。與Jurdzinski等人所提出的算法DetGenBroadcast相比，TEGB在時(shí)間性能上改進(jìn)了一個(gè)對(duì)數(shù)因子。為了減少?gòu)V播消息的冗余傳播，提出了第二個(gè)廣播算法（the Tree-Based Global Broadcast，TBGB）。算法TBGB可以構(gòu)造網(wǎng)絡(luò)的單向生成樹(shù)，在該生成樹(shù)中，只有非葉子節(jié)點(diǎn)需要轉(zhuǎn)發(fā)廣播消息。與TEGB相比，TBGB可以大大降低廣播消息的冗余傳

5、播。理論分析表明，TBGB的時(shí)間復(fù)雜度為O(DΔlogn)，這里Δ為最大節(jié)點(diǎn)度。仿真結(jié)果驗(yàn)證了以上的理論分析。
　　(2)在異步通訊模型下，設(shè)計(jì)了基于擴(kuò)展物理干擾模型的分布式多消息廣播算法（the Distributed Asynchronous Multiple-message Broadcast，DAMB）。基于一個(gè)預(yù)先定義的傳輸骨干結(jié)構(gòu)，算法DAMB可以在1)])2(([log n+ c? D+k?τO時(shí)間內(nèi)解決多消息廣播問(wèn)