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

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

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

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