連通控制集的構(gòu)造與維護(hù)算法研究.pdf

1、無線傳感器網(wǎng)絡(luò)是由一組帶有無線收發(fā)設(shè)備的傳感器節(jié)點(diǎn)組成的多跳的臨時(shí)性無中心網(wǎng)絡(luò)，可以在任何時(shí)刻、任何地點(diǎn)、快速的構(gòu)建起一個(gè)移動(dòng)通信網(wǎng)絡(luò)，并且不需要現(xiàn)有網(wǎng)絡(luò)基礎(chǔ)設(shè)施的支持。一個(gè)典型的傳感器節(jié)點(diǎn)一般由傳感系統(tǒng)、處理系統(tǒng)、無線通信系統(tǒng)和能源設(shè)備構(gòu)成。傳感系統(tǒng)用來獲取周圍環(huán)境中的數(shù)據(jù)；處理系統(tǒng)用于本地?cái)?shù)據(jù)處理和存儲(chǔ)；無線通信系統(tǒng)用來進(jìn)行數(shù)據(jù)傳輸；能源設(shè)備則用于提供系統(tǒng)完成任務(wù)所需要的能量。
　　 在無線傳感器網(wǎng)絡(luò)中，節(jié)點(diǎn)不僅要負(fù)責(zé)通信任

2、務(wù)，同時(shí)還要擔(dān)當(dāng)路由功能。而基于洪泛的路由機(jī)制會(huì)引起廣播風(fēng)暴問題，這將消耗大量的網(wǎng)絡(luò)資源。由于網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)動(dòng)態(tài)變化性、多跳通信特性和資源的有限性，合理的路由設(shè)計(jì)成了一個(gè)挑戰(zhàn)性的問題。對此，許多學(xué)者提出了構(gòu)造虛擬骨干網(wǎng)，將網(wǎng)絡(luò)分級來實(shí)現(xiàn)網(wǎng)絡(luò)的穩(wěn)定性和高效性。通過在無線傳感器網(wǎng)絡(luò)中構(gòu)造虛擬骨干網(wǎng)即可將網(wǎng)絡(luò)中節(jié)點(diǎn)進(jìn)行分級，而這一過程正是圖論中連通控制集理論的一個(gè)應(yīng)用。可以將路由簡化到由最小連通控制集構(gòu)造成的虛擬骨干網(wǎng)中去。信息由源節(jié)點(diǎn)出發(fā)，沿

3、著連通控制集中的節(jié)點(diǎn)傳遞到離目的節(jié)點(diǎn)最近的控制節(jié)點(diǎn)，最終到達(dá)目的節(jié)點(diǎn)。
　　 本文以連通控制集作為研究問題的理論基礎(chǔ)，對傳統(tǒng)的構(gòu)造連通控制集的方法進(jìn)行了深入研究，并在現(xiàn)有算法的基礎(chǔ)上提出了一個(gè)改進(jìn)最小連通控制集算法，該算法首先構(gòu)造一個(gè)極大獨(dú)立集，在此基礎(chǔ)上利用兩跳局部網(wǎng)絡(luò)信息選擇連通點(diǎn)，形成連通控制集。對于構(gòu)造連通控制集的算法，有以下四個(gè)方面的因素度量算法的性能：近似比、局部性、時(shí)間復(fù)雜度和消息復(fù)雜度、以及穩(wěn)定性。理論和仿真實(shí)驗(yàn)

4、都表明，本文所提出的改進(jìn)的算法與現(xiàn)有的算法相比，能得到一個(gè)更小的虛擬骨干網(wǎng)，即有更小的近似比6.906。
　　 近年來，為了適應(yīng)無線網(wǎng)絡(luò)的復(fù)雜環(huán)境，具有更好容錯(cuò)性，更強(qiáng)健壯性的k-連通m-控制集問題及其構(gòu)造算法也相繼出現(xiàn)。但是，大多數(shù)構(gòu)造算法在面臨網(wǎng)絡(luò)中節(jié)點(diǎn)的移動(dòng)時(shí)都要重新構(gòu)造kmCDS，這無疑增加了開銷。基于此本文還給出了一個(gè)移動(dòng)情況下k-連通m-控制集的維護(hù)算法。在由現(xiàn)有算法構(gòu)造出kmCDS骨干網(wǎng)的無線網(wǎng)絡(luò)中，當(dāng)節(jié)點(diǎn)移動(dòng)時(shí)，