【摘要】：隨著無(wú)線網(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ò)生命周期的瓶頸問(wèn)題。因此,為了增大整個(gè)網(wǎng)絡(luò)在探測(cè)區(qū)域內(nèi)的生命周期,我們應(yīng)該盡可能的節(jié)省節(jié)點(diǎn)能量消耗。然而,當(dāng)網(wǎng)絡(luò)節(jié)點(diǎn)通過(guò)廣播的方式與鄰居節(jié)點(diǎn)通信的過(guò)程中會(huì)造成大量的信息冗余,不僅會(huì)導(dǎo)致信息的傳遞不成功,而且也極大的造成了節(jié)點(diǎn)的能量損耗。為了減少節(jié)點(diǎn)通信過(guò)程中產(chǎn)生的信息冗余和節(jié)點(diǎn)的能量損耗,最簡(jiǎn)單有效的方法是建立網(wǎng)絡(luò)中的虛擬骨干網(wǎng)絡(luò),也就是連通控制集(CDS)。目前,在無(wú)線網(wǎng)絡(luò)中構(gòu)造連通控制集的一些經(jīng)典算法多數(shù)包含兩個(gè)階段。在算法的第一個(gè)階段構(gòu)造網(wǎng)絡(luò)的一個(gè)極大獨(dú)立集(MIS)。在第二個(gè)階段,通過(guò)從V\MIS中選取一定的節(jié)點(diǎn)作為連通節(jié)點(diǎn)加入到MIS中,使得MIS中的節(jié)點(diǎn)都有路徑相連。在本文中,首先對(duì)現(xiàn)有的一些經(jīng)典的連通控制集算法進(jìn)行研究與分析,然后在單位圓盤圖(UDG)上提出了構(gòu)造連通控制集的分布式算法LDDS和CT算法。之后,又提出了算法LDDS的集中式版本算法CMDS,并提出了連通CMDS構(gòu)造的控制集MDS的集中式連通算法CMCDS。然后,對(duì)一般的圖模型,我們得到了一個(gè)最優(yōu)連通控制集MCDS的一個(gè)下界,也就是,從而證明了對(duì)于任意的連通控制集的近似因子。最后,在一般的圖上構(gòu)造了分布式算法Asyn_BFS、COF、CMIS、ACP、ACHC、PMIS和全局連通算法,得到了相對(duì)較優(yōu)的連通控制集。本文主要分為六章。第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í),則直接將節(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_BFS得到了一個(gè)寬度優(yōu)先搜索樹(shù)。然后,提出的COF算法在網(wǎng)絡(luò)中根據(jù)節(jié)點(diǎn)的度構(gòu)造了一個(gè)森林。算法CMIS在森林中每棵樹(shù)上得到一個(gè)局部的MIS。算法ACP則根據(jù)MIS中節(jié)點(diǎn)的個(gè)數(shù)將將每棵樹(shù)劃分為|MIS|個(gè)簇。算法ACHC將每棵樹(shù)上|MIS|個(gè)簇的簇頭連通。算法PMIS則將所求局部CDS中冗余的節(jié)點(diǎn)裁剪掉。最后全局連通算法將所有的局部控制集連通。第6章對(duì)本文進(jìn)行總結(jié),并對(duì)未來(lái)進(jìn)一步的研究工作進(jìn)行了展望。
[Abstract]:......
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TN92

【相似文獻(xiàn)】

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

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

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

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

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

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

6 ;[J];;年期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

，

本文編號(hào)：2464508