基于無線傳感器網絡的spanner研究.pdf

1、無線傳感器網絡是具有監(jiān)測、控制和無線通信等功能的綜合網絡系統(tǒng)，通過將大量傳感器節(jié)點隨機部署在需要監(jiān)測的區(qū)域內，由各節(jié)點間自組織構成網絡。一般來說，傳感器節(jié)點一旦部署后位置便不會再變動，此外，傳感器節(jié)點本身具有的能量也是極為有限的且各節(jié)點間通信必然存在一定的物理干擾，這些因素都會影響網絡的通信質量。在這種環(huán)境下，spanner技術應運而生。
　　本文主要研究的是在保證無線傳感器網絡的連通性條件下，盡可能將無線網絡節(jié)點間的通信鏈路稀疏

2、化，從而達到減少組網開銷和通信干擾的目的，最終完成對無線傳感器網絡的優(yōu)化，這就是spanner技術的關鍵。Spanner實質是一種稀疏圖，是將無線網絡問題轉化為圖問題加以研究，其中網絡的節(jié)點對應為圖中的頂點，各節(jié)點之間的鏈路對應為圖中的邊，從而將網絡優(yōu)化問題轉化為求對應完全圖的相對稀疏圖過程：首先將網絡中的所有節(jié)點定義為圖中的頂點，尋找任意兩頂點間的 t-path；然后利用單元最短路徑算法查詢其他節(jié)點間的鏈路，根據支撐比定義，將新的鏈路

3、標記為新的 t-path；以此類推，最后得到一個關于網絡的spanner，這就需要涉及到算法來構造spanner。本篇論文是在經典 greedy算法的基礎上，利用 WSPD數據結構和權值矩陣進行算法的改進，從而得出較為先進的TB-Greedy算法，并且在加倍度量空間中，利用啞鈴定理與WSPD的性質以及支撐因子，證明了該算法的正確性與現實操作中的可行性。最后本篇論文又從理論擴展到實際，在TB-Greedy算法執(zhí)行過程中又提出了節(jié)點間的物理

4、干擾問題，從而使得我們的算法更接近于實際應用環(huán)境。論文下一步進行的工作是如何進一步減少算法的空間復雜度，從而使TB-Greedy成為更為接近最優(yōu)的spanner構造算法。
　　通過我們的大量研究工作，可以主要得出以下結論：TB-Greedy算法在保證網絡連通的條件下，所求的 spanner相對稀疏，并且時間復雜度有較大的提升；同時又減少了組網開銷和節(jié)點間的物理干擾問題。我們又通過實驗仿真，很好的驗證了TB-Greedy算法正確性與