無線網(wǎng)絡(luò)中連通控制集的算法設(shè)計(jì)與分析.pdf

1、隨著無線網(wǎng)絡(luò)在家庭自動(dòng)化、交通控制、醫(yī)療保健、環(huán)境監(jiān)測(cè)、戰(zhàn)場(chǎng)探測(cè)和農(nóng)業(yè)等方面的應(yīng)用，因?yàn)榫W(wǎng)絡(luò)節(jié)點(diǎn)是由電池供電，所以節(jié)點(diǎn)自身存在的能量幾乎成為網(wǎng)絡(luò)生命周期的瓶頸問題。因此，為了增大整個(gè)網(wǎng)絡(luò)在探測(cè)區(qū)域內(nèi)的生命周期，我們應(yīng)該盡可能的節(jié)省節(jié)點(diǎn)能量消耗。然而，當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)通過廣播的方式與鄰居節(jié)點(diǎn)通信的過程中會(huì)造成大量的信息冗余，不僅會(huì)導(dǎo)致信息的傳遞不成功，而且也極大的造成了節(jié)點(diǎn)的能量損耗。為了減少節(jié)點(diǎn)通信過程中產(chǎn)生的信息冗余和節(jié)點(diǎn)的能量損耗，最簡(jiǎn)單

2、有效的方法是建立網(wǎng)絡(luò)中的虛擬骨干網(wǎng)絡(luò)，也就是連通控制集（CDS）。目前，在無線網(wǎng)絡(luò)中構(gòu)造連通控制集的一些經(jīng)典算法多數(shù)包含兩個(gè)階段。在算法的第一個(gè)階段構(gòu)造網(wǎng)絡(luò)的一個(gè)極大獨(dú)立集(MIS)。在第二個(gè)階段，通過從 V\MIS中選取一定的節(jié)點(diǎn)作為連通節(jié)點(diǎn)加入到 MIS中，使得MIS中的節(jié)點(diǎn)都有路徑相連。
　　在本文中，首先對(duì)現(xiàn)有的一些經(jīng)典的連通控制集算法進(jìn)行研究與分析，然后在單位圓盤圖(UDG)上提出了構(gòu)造連通控制集的分布式算法LDDS和C

3、T算法。之后，又提出了算法LDDS的集中式版本算法CMDS，并提出了連通CMDS構(gòu)造的控制集MDS的集中式連通算法 CMCDS。然后，對(duì)一般的圖模型，我們得到了一個(gè)最優(yōu)連通控制集MCDS的一個(gè)下界n-1/△-1/2，也就是MCDS>n-1/△-1/2，從而證明了對(duì)于任意的連通控制集的近似因子p<△-1/2。最后，在一般的圖上構(gòu)造了分布式算法Asyn_BFS、COF、CMIS、ACP、ACHC、PMIS和全局連通算法，得到了相對(duì)較優(yōu)的連通

4、控制集。
　　本文主要分為六章。第1章介紹了研究背景、意義和構(gòu)造連通控制集需要考慮的性能指標(biāo)。第2章對(duì)當(dāng)前的一些連通控制集算法及相關(guān)結(jié)果進(jìn)行了簡(jiǎn)單分類和總結(jié)，并對(duì)其中的一些構(gòu)造算法進(jìn)行了簡(jiǎn)單的分析。第3章在單位圓盤圖上設(shè)計(jì)了一個(gè)求解近似最小連通控制集的分布式算法。首先設(shè)計(jì)了一個(gè)求解最小控制集的近似算法LDDS，該算法根據(jù)鏈路的最大鄰邊的數(shù)目成對(duì)的選出控制集的節(jié)點(diǎn)，當(dāng)存在一個(gè)節(jié)點(diǎn)v的N(v)中所有節(jié)點(diǎn)的鄰居節(jié)點(diǎn)都在N(v)中時(shí)，則直

5、接將節(jié)點(diǎn)v加入到控制集中。之后，提出了一個(gè)Connecting Tree構(gòu)造算法CT，使得連通控制集中的節(jié)點(diǎn)需要的連通節(jié)點(diǎn)盡量的少。第4章提出了算法LDDS的集中式版本算法CMDS，得到了一個(gè)最小的控制集MDS。之后，我們?cè)O(shè)計(jì)了一個(gè)集中式連通算法CMCDS，貪心地往MDS中增加節(jié)點(diǎn)使得控制集MDS中的所有節(jié)點(diǎn)連通。這里CMCDS算法是選擇最少的連通節(jié)點(diǎn)的算法。第5章在一般的圖模型上設(shè)計(jì)了一個(gè)求解連通控制集的分布式算法。首先算法Asyn_