基于連通支配集的無線傳感器虛擬骨干網(wǎng)近似算法研究.pdf

1、無線傳感器網(wǎng)絡(luò)(Wireless Sensor Network，WSN)一般是指大規(guī)模的無線傳感器節(jié)點(diǎn)以自組織的形式所構(gòu)成的網(wǎng)絡(luò)系統(tǒng)。它能夠利用無線傳感器實(shí)時(shí)地采集特定區(qū)域內(nèi)的有效信息，并且將信息通過無線網(wǎng)絡(luò)以多跳的方式傳遞到匯聚節(jié)點(diǎn)，從而實(shí)現(xiàn)追蹤和監(jiān)視對(duì)象的功能。基于以上特點(diǎn)使得無線傳感器網(wǎng)絡(luò)廣泛應(yīng)用在很多重點(diǎn)領(lǐng)域，如軍事、醫(yī)療、智能家居等。
　　關(guān)于無線傳感器網(wǎng)絡(luò)，一方面由于廣播操作通常使用洪泛來完成，在不受限制的情況下，很可

2、能會(huì)帶來廣播風(fēng)暴問題。另一方面?zhèn)鞲衅鞴?jié)點(diǎn)的資源也有限。針對(duì)以上情況，研究者們提出了運(yùn)用連通支配集理論來形成虛擬骨干網(wǎng)的思想。只有骨干節(jié)點(diǎn)負(fù)責(zé)數(shù)據(jù)的存儲(chǔ)轉(zhuǎn)發(fā)，而非骨干節(jié)點(diǎn)不進(jìn)行工作時(shí)，可將自身通信模塊關(guān)閉以達(dá)到節(jié)省能量的目的。這樣不僅可以使無線傳感器網(wǎng)絡(luò)減少路由開銷，均衡能量消耗，還可以提高廣播效率，增強(qiáng)自組織性。
　　本文以無線傳感器網(wǎng)絡(luò)的隨機(jī)分布、大規(guī)模部署和同構(gòu)拓?fù)錇槌霭l(fā)點(diǎn)，把連通支配集理論作為研究基礎(chǔ)，在綜合考慮了節(jié)點(diǎn)的剩余

3、能量和度等因素后，設(shè)計(jì)了一個(gè)參考能量的最小連通支配集集中式算法(MCDS-EC)。MCDS-EC算法定義了合理的權(quán)值公式，并且根據(jù)每個(gè)節(jié)點(diǎn)的權(quán)值大小建立頂點(diǎn)次序表，省去了集中式算法中普遍采用的構(gòu)造樹的過程。MCDS-EC算法的時(shí)間復(fù)雜度為O(n3)。仿真實(shí)驗(yàn)表明，該算法構(gòu)造的連通支配集在規(guī)模大小及網(wǎng)絡(luò)生命期兩個(gè)方面都比相關(guān)文獻(xiàn)中的算法更有效。
　　此外，本文還提出一種均衡能量的最小連通支配集分布式算法(MCD S-ED)。MCDS

4、-ED算法是一種基于鄰節(jié)點(diǎn)信息的算法，需要獲知兩跳范圍內(nèi)的節(jié)點(diǎn)信息。由于通信距離直接關(guān)系到節(jié)點(diǎn)的能量消耗，所以在設(shè)置權(quán)值參數(shù)時(shí)，除了考慮節(jié)點(diǎn)剩余能量和度，還考慮了節(jié)點(diǎn)與其鄰節(jié)點(diǎn)的平均通信距離。同時(shí)為進(jìn)一步均衡網(wǎng)絡(luò)能量消耗，MCDS-ED算法為每個(gè)節(jié)點(diǎn)設(shè)置能量監(jiān)視器，一旦節(jié)點(diǎn)能量低于閾值將退出虛擬骨干網(wǎng)，并且算法將重新尋找新的骨干節(jié)點(diǎn)。MCDS-ED算法的時(shí)間復(fù)雜度是O(n2），消息復(fù)雜度是O(n△)。其中△是圖G中節(jié)點(diǎn)的的最大度，在理論