無線傳感器網(wǎng)絡中基于樹的負載平衡算法研究.pdf

1、隨著微機電系統(tǒng)、片上系統(tǒng)、通信技術和低能耗嵌入式技術的快速發(fā)展,無線傳感器網(wǎng)絡(WSN)應運而生,已經(jīng)成為計算機科學與技術的一個新興領域。它有十分廣闊的使用前景,目前已經(jīng)應用到農(nóng)業(yè)、軍事、醫(yī)療、商業(yè)、環(huán)境等系統(tǒng)的各個方面。
　　由于傳感器節(jié)點自身攜帶能量低、不可充能、無人值守等特點,極大程度限制了無線傳感器網(wǎng)絡的工作時間。在不知道節(jié)點具體位置的情況下如何建立一個高效連通的網(wǎng)絡是目前面臨的一個重要問題。
　　本文針對WSN中的

2、數(shù)據(jù)收集問題,以最大化網(wǎng)絡生命周期為目的,在分析了大量網(wǎng)絡協(xié)議的基礎上,對不同類型的數(shù)據(jù)收集進行研究,建立不同的模型,提出了兩種不同算法,并通過仿真實驗驗證算法性能。本文具體做了以下兩方面工作:
　?、籴槍_數(shù)據(jù)收集,在不知道節(jié)點位置信息的情況下,提出一個網(wǎng)絡負載平衡算法(LBAPDG)。它以最大化網(wǎng)絡生命周期為目標,用多項式啟發(fā)算法求解了一個需要構造最優(yōu)生成樹的NP完全問題。該算法首先通過Sink節(jié)點構造一棵具有最多孩子的生成

3、樹,在這棵樹的基礎上,采用宏觀的廣度優(yōu)先搜索不斷轉(zhuǎn)移瓶頸節(jié)點的子孫到其它負載較輕的節(jié)點上,網(wǎng)絡負載依次從第一層節(jié)點開始逐層向下進行平衡,底層節(jié)點進行轉(zhuǎn)移時不能影響高層的負載平衡,只能在某一子樹內(nèi)部進行轉(zhuǎn)移。該算法以層為單位平衡網(wǎng)絡的負載。
　　②針對相關數(shù)據(jù)收集不能用LBAPDG算法解決的問題,提出了一個LBACDG算法。它以最大化網(wǎng)絡生命周期為目標,根據(jù)稠密網(wǎng)絡特點利用接收發(fā)送功率之間的相互關系,簡化了網(wǎng)絡模型。該算法通過貪心策