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

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

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

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

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

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