無線傳感器網絡中分布式廣播算法研究.pdf

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

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

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

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

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