AdHoc傳感器網(wǎng)絡(luò)中連通支配集算法的研究.pdf

1、AdHoc傳感器網(wǎng)絡(luò)是一種具有大規(guī)模性、自組織性、無基礎(chǔ)設(shè)施支持等特點的網(wǎng)絡(luò)，能夠應(yīng)用于各個領(lǐng)域，具有重要的現(xiàn)實意義。該網(wǎng)絡(luò)利用連通支配集作為虛擬網(wǎng)絡(luò)骨干，以此來進行數(shù)據(jù)聚合和網(wǎng)絡(luò)節(jié)點通信，實現(xiàn)網(wǎng)絡(luò)的廣播和路由。本文針對在AdHoc傳感器網(wǎng)絡(luò)中構(gòu)建最小連通支配集進行了如下研究，通過分析現(xiàn)有算法，得出目前效果較好的求解連通支配集的方法是基于二階段的方法，因此本文針對其求解過程的兩個階段提出了三種改進的算法。
　　針對第一階段-求解M

2、IS（極大獨立集）階段，本文分析了現(xiàn)有的基于協(xié)同覆蓋的最小連通支配集算法。該類算法的協(xié)同覆蓋思想雖然可以使問題接近最優(yōu)解，但也降低了覆蓋效率。本文對此進行改進，采用新的支配點選擇方案，優(yōu)先從當(dāng)前支配節(jié)點的三跳鄰居中選擇下一個支配節(jié)點，如果不存在，則從當(dāng)前支配節(jié)點的兩跳鄰居中選擇下一個支配節(jié)點，使覆蓋盡可能少的存在交集，增大覆蓋效率。
　　針對第二階段-斯坦納樹構(gòu)建階段，多數(shù)算法均采用貪心方式尋找斯坦納節(jié)點，該類算法簡單但容易陷入局

3、部最優(yōu)解。本文對此進行改進，在斯坦納節(jié)點的選擇上了進行了相應(yīng)的權(quán)值處理同時加入了檢測處理階段，即檢測是否存在冗余的節(jié)點。提出了兩種改進的斯坦納樹構(gòu)建算法-IK-ST算法和ML-ST算法。進一步降低了支配集的規(guī)模。
　　仿真實驗中，首先對比了IC-MIS算法和Rajiv Misra提出的算法，通過比較所求得的MIS的節(jié)點數(shù)目來衡量算法的優(yōu)劣，接著通過IK-ST和ML-ST算法優(yōu)化Rajiv Misra算法的斯坦納樹構(gòu)建階段，然后與其