基于無線傳感器網(wǎng)絡(luò)的spanner研究.pdf

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

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

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

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