準組Steiner樹在無線自組網(wǎng)中的應用.pdf

1、無線Mesh網(wǎng)絡(luò)和無線傳感器網(wǎng)絡(luò)是兩類特殊的無線自組織網(wǎng)絡(luò)。無線Mesh網(wǎng)絡(luò)主要應用于替代傳統(tǒng)的用于連接最終用戶的最后一英里線路，以降低接入用戶的布線成本。無線傳感器網(wǎng)絡(luò)則主要應用于環(huán)境檢測、目標跟蹤、戰(zhàn)場監(jiān)視等目的。 在無線Mesh網(wǎng)絡(luò)中，仍然需要一個由有線網(wǎng)絡(luò)組成的骨干網(wǎng)絡(luò)用以連接Internet和無線接入點，因此仍然需要特定形式的布線優(yōu)化。本文將其抽象為特殊的數(shù)學模型，并給出了近似算法。在無線傳感器網(wǎng)絡(luò)中，較之普通的無線自

2、組網(wǎng)節(jié)點的能量和計算能力更為有限，計算能力也相對較低，因此節(jié)能策略更為急迫。本文在充分考慮數(shù)據(jù)融合等需求后，提出了一種多播節(jié)能策略，并且給出了實現(xiàn)協(xié)議。 本文的主要內(nèi)容與貢獻有： a)通過討論用戶節(jié)點的需求和無線連接層的約束，將優(yōu)化無線Mesh網(wǎng)絡(luò)中的骨干網(wǎng)絡(luò)的問題抽象為準組Steiner樹模型；證明了該問題是NP難的，并且給出了在最壞情況多項式算法的近似比下限。 b)根據(jù)不同的策略給出了三種不同的近似算法一基于