【摘要】：隨著無線網(wǎng)絡(luò)在家庭自動化、交通控制、醫(yī)療保健、環(huán)境監(jiān)測、戰(zhàn)場探測和農(nóng)業(yè)等方面的應(yīng)用,因為網(wǎng)絡(luò)節(jié)點是由電池供電,所以節(jié)點自身存在的能量幾乎成為網(wǎng)絡(luò)生命周期的瓶頸問題。因此,為了增大整個網(wǎng)絡(luò)在探測區(qū)域內(nèi)的生命周期,我們應(yīng)該盡可能的節(jié)省節(jié)點能量消耗。然而,當(dāng)網(wǎng)絡(luò)節(jié)點通過廣播的方式與鄰居節(jié)點通信的過程中會造成大量的信息冗余,不僅會導(dǎo)致信息的傳遞不成功,而且也極大的造成了節(jié)點的能量損耗。為了減少節(jié)點通信過程中產(chǎn)生的信息冗余和節(jié)點的能量損耗,最簡單有效的方法是建立網(wǎng)絡(luò)中的虛擬骨干網(wǎng)絡(luò),也就是連通控制集(CDS)。目前,在無線網(wǎng)絡(luò)中構(gòu)造連通控制集的一些經(jīng)典算法多數(shù)包含兩個階段。在算法的第一個階段構(gòu)造網(wǎng)絡(luò)的一個極大獨立集(MIS)。在第二個階段,通過從V\MIS中選取一定的節(jié)點作為連通節(jié)點加入到MIS中,使得MIS中的節(jié)點都有路徑相連。在本文中,首先對現(xiàn)有的一些經(jīng)典的連通控制集算法進(jìn)行研究與分析,然后在單位圓盤圖(UDG)上提出了構(gòu)造連通控制集的分布式算法LDDS和CT算法。之后,又提出了算法LDDS的集中式版本算法CMDS,并提出了連通CMDS構(gòu)造的控制集MDS的集中式連通算法CMCDS。然后,對一般的圖模型,我們得到了一個最優(yōu)連通控制集MCDS的一個下界,也就是,從而證明了對于任意的連通控制集的近似因子。最后,在一般的圖上構(gòu)造了分布式算法Asyn_BFS、COF、CMIS、ACP、ACHC、PMIS和全局連通算法,得到了相對較優(yōu)的連通控制集。本文主要分為六章。第1章介紹了研究背景、意義和構(gòu)造連通控制集需要考慮的性能指標(biāo)。第2章對當(dāng)前的一些連通控制集算法及相關(guān)結(jié)果進(jìn)行了簡單分類和總結(jié),并對其中的一些構(gòu)造算法進(jìn)行了簡單的分析。第3章在單位圓盤圖上設(shè)計了一個求解近似最小連通控制集的分布式算法。首先設(shè)計了一個求解最小控制集的近似算法LDDS,該算法根據(jù)鏈路的最大鄰邊的數(shù)目成對的選出控制集的節(jié)點,當(dāng)存在一個節(jié)點v的N(v)中所有節(jié)點的鄰居節(jié)點都在N(v)中時,則直接將節(jié)點v加入到控制集中。之后,提出了一個Connecting Tree構(gòu)造算法CT,使得連通控制集中的節(jié)點需要的連通節(jié)點盡量的少。第4章提出了算法LDDS的集中式版本算法CMDS,得到了一個最小的控制集MDS。之后,我們設(shè)計了一個集中式連通算法CMCDS,貪心地往MDS中增加節(jié)點使得控制集MDS中的所有節(jié)點連通。這里CMCDS算法是選擇最少的連通節(jié)點的算法。第5章在一般的圖模型上設(shè)計了一個求解連通控制集的分布式算法。首先算法Asyn_BFS得到了一個寬度優(yōu)先搜索樹。然后,提出的COF算法在網(wǎng)絡(luò)中根據(jù)節(jié)點的度構(gòu)造了一個森林。算法CMIS在森林中每棵樹上得到一個局部的MIS。算法ACP則根據(jù)MIS中節(jié)點的個數(shù)將將每棵樹劃分為|MIS|個簇。算法ACHC將每棵樹上|MIS|個簇的簇頭連通。算法PMIS則將所求局部CDS中冗余的節(jié)點裁剪掉。最后全局連通算法將所有的局部控制集連通。第6章對本文進(jìn)行總結(jié),并對未來進(jìn)一步的研究工作進(jìn)行了展望。
[Abstract]:......
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TN92

【相似文獻(xiàn)】

相關(guān)期刊論文 前6條

1 張志強(qiáng);葉安勝;周曉清;;最小控制集問題的群集策略智能算法研究[J];科學(xué)技術(shù)與工程;2014年16期

2 ;工程數(shù)學(xué)[J];中國無線電電子學(xué)文摘;2005年02期

3 曹建香;稅琳琳;石民勇;;廣義道路與廣義圈的綁定數(shù)與增強(qiáng)數(shù)[J];中國傳媒大學(xué)學(xué)報(自然科學(xué)版);2007年02期

4 David Crump;;氫生產(chǎn)的控制集成[J];軟件;2010年06期

5 李峰;趙海興;徐宗本;;構(gòu)建一類新網(wǎng)絡(luò)簇的可靠性控制集[J];計算機(jī)學(xué)報;2013年06期

6 ;[J];;年期

相關(guān)重要報紙文章 前2條

1 石家莊市畜牧水產(chǎn)局 趙洪明　強(qiáng)慧勤 王榮申 張濤 李釗;養(yǎng)殖投入品控制集成技術(shù)[N];河北科技報;2013年

2 宦建新　通訊員　沈維強(qiáng);浙江“食品安全科技專項”取得成果[N];科技日報;2005年

相關(guān)博士學(xué)位論文 前10條

1 趙維勝;關(guān)于樹的控制問題與強(qiáng)乘積圖約束數(shù)的研究[D];蘭州大學(xué);2015年

2 董艷俠;廣義de Bruijn有向圖和超圖的控制集問題[D];上海大學(xué);2016年

3 彭茂;圖的控制集的一些相關(guān)問題的研究[D];上海交通大學(xué);2008年

4 陳磊;圖中配對控制集問題的機(jī)械化算法研究[D];華東師范大學(xué);2010年

5 劉清海;幾類組合優(yōu)化問題的算法研究[D];新疆大學(xué);2012年

6 李憲越;關(guān)于一些網(wǎng)絡(luò)最優(yōu)化問題的近似算法的研究[D];蘭州大學(xué);2009年

7 黃佳;圖的控制穩(wěn)定性研究[D];中國科學(xué)技術(shù)大學(xué);2007年

8 陳星;幾類圖的連通性和控制集[D];新疆大學(xué);2011年

9 胡夫濤;圖的約束數(shù)研究[D];中國科學(xué)技術(shù)大學(xué);2012年

10 陸由;圖的控制理論研究[D];中國科學(xué)技術(shù)大學(xué);2010年

相關(guān)碩士學(xué)位論文 前10條

1 秦敏艷;路和圈的定位控制集問題[D];華東師范大學(xué);2010年

2 羅傳文;無線網(wǎng)絡(luò)中連通控制集的算法設(shè)計與分析[D];曲阜師范大學(xué);2016年

3 丁玲玲;圖的控制集問題的近似算法研究[D];中國海洋大學(xué);2008年

4 陳春霞;關(guān)于路和圈的驗證碼和定位控制集問題[D];華東師范大學(xué);2009年

5 李秀英;求最小2連通r步控制集的兩種算法[D];新疆大學(xué);2011年

6 何永能;圖的電力控制集問題[D];華東師范大學(xué);2012年

7 盛斌;立方圖的配對控制集問題上界[D];華東師范大學(xué);2013年

8 楊曉靜;圖的[1,2]-控制集[D];新疆大學(xué);2014年

9 麻娜;圖的控制參數(shù)的若干問題[D];大連理工大學(xué);2001年

10 吳亞娜;無爪圖配對控制集問題上界的研究[D];華東師范大學(xué);2013年

，

本文編號：2464508