本文關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)中連通控制集問題的研究

  更多相關(guān)文章： 無線傳感器網(wǎng)絡(luò) 圓盤圖 最小k-連通m-控制集 最小m-連通k-全控制集

【摘要】： 隨著傳感器技術(shù)的快速發(fā)展和大眾對(duì)無線傳感器網(wǎng)絡(luò)(wireless sensor network, WSN)應(yīng)用前景的日益重視,國內(nèi)外對(duì)無線傳感器網(wǎng)絡(luò)的研究越來越多、越來越深入。其中,由于無線傳感器網(wǎng)絡(luò)是一個(gè)沒有基礎(chǔ)設(shè)施的自組織無線移動(dòng)網(wǎng)絡(luò)并且傳感器網(wǎng)絡(luò)中的節(jié)點(diǎn)很容易發(fā)生故障或者能量耗盡導(dǎo)致通信中斷。因此,在網(wǎng)絡(luò)中通過建立多連通多控制集來構(gòu)造容錯(cuò)的虛擬骨干(virtual backbone)來負(fù)責(zé)數(shù)據(jù)的路由轉(zhuǎn)發(fā)成為目前學(xué)術(shù)界的一個(gè)熱點(diǎn)問題。 鑒于傳感器網(wǎng)絡(luò)具有很好的平面結(jié)構(gòu)和連通控制集的良好性質(zhì),本文主要在圓盤圖中研究了傳感器網(wǎng)絡(luò)的最小多連通多控制集問題。首先,本文對(duì)現(xiàn)有的連通控制集問題進(jìn)行了分析和總結(jié)。其次,本文在現(xiàn)有的理論成果的基礎(chǔ)上,給出了針對(duì)在節(jié)點(diǎn)傳輸半徑可變的一般圓盤圖中的最小k-連通m-控制集問題的新型算法和新型分析方法。該算法主要分為四步：一、用貪婪算法和染色機(jī)制構(gòu)造一個(gè)連通控制集；二、通過不斷地選擇極大獨(dú)立集k-1次構(gòu)造一個(gè)k-控制集,使得除了控制集外的每個(gè)節(jié)點(diǎn)被控制集中至少k個(gè)節(jié)點(diǎn)所控制；三、用貪婪算法選擇連通控制集中的節(jié)點(diǎn),通過選取塊k-1次使得連通k-控制集k-連通；四、選擇極大獨(dú)立集m-k次構(gòu)造k-連通m-控制集(其中,k,m為任意正整數(shù)且m不小于k),并通過理論分析得到該近似算法的近似比。最后,我們提出了新的研究模型,即在節(jié)點(diǎn)傳輸半徑可變的圓盤圖中研究最小m-連通k-全控制集問題(其中,k,m為任意正整數(shù)),對(duì)這一問題給出新的算法并進(jìn)行了理論分析。
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2010
【分類號(hào)】：TN929.5;TP212.9

【共引文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前10條

1 王琳珠;范亞芹;胡可剛;;基于Ad Hoc的有效廣播路由算法[J];吉林大學(xué)學(xué)報(bào)(信息科學(xué)版);2009年01期

2 張靜,孫雨耕,房朝暉;能量有效的最小連通支配集近似算法[J];傳感技術(shù)學(xué)報(bào);2004年04期

3 孫彥景;錢建生;顧相平;陳光柱;;聯(lián)合約束無線傳感器網(wǎng)絡(luò)連通支配集算法[J];電子科技大學(xué)學(xué)報(bào);2009年02期

4 孫彥景;錢建生;顧相平;陳光柱;;時(shí)延和功耗約束無線傳感器網(wǎng)絡(luò)連通支配集算法(英文)[J];Journal of Southeast University(English Edition);2008年04期

5 唐勇;周明天;;基于極大獨(dú)立集的最小連通支配集的分布式算法[J];電子學(xué)報(bào);2007年05期

6 許力,鄭寶玉;MANET環(huán)境下基于能量保護(hù)的路由策略及其研究進(jìn)展[J];電子與信息學(xué)報(bào);2005年05期

7 譚國真;黃利華;;基于骨干子網(wǎng)內(nèi)競爭的Internet自治域?qū)友莼Ｐ蚚J];復(fù)雜系統(tǒng)與復(fù)雜性科學(xué);2007年03期

8 陳濤;郭得科;羅雪山;陳洪輝;;一種基于移動(dòng)基站的無線傳感器網(wǎng)絡(luò)數(shù)據(jù)收集方法[J];國防科技大學(xué)學(xué)報(bào);2011年02期

9 鄭嬋;尹令;張義青;;監(jiān)測(cè)奶牛無線傳感器網(wǎng)絡(luò)的連通支配集構(gòu)造[J];廣西大學(xué)學(xué)報(bào)(自然科學(xué)版);2012年02期

10 王玉明;趙大勝;;基于串行最大獨(dú)立集的連通支配集構(gòu)造及分析[J];華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 劉卓;無線傳感器網(wǎng)絡(luò)拓?fù)浣⒎椒ㄅc應(yīng)用技術(shù)研究[D];華中科技大學(xué);2011年

2 趙楠楠;無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ㄑ芯縖D];北京郵電大學(xué);2011年

3 汪文勇;無線傳感器網(wǎng)絡(luò)若干節(jié)能關(guān)鍵技術(shù)研究[D];電子科技大學(xué);2011年

4 焦賢龍;無線自組網(wǎng)廣播與數(shù)據(jù)聚合算法研究[D];國防科學(xué)技術(shù)大學(xué);2011年

5 王旭東;基于圖論的智能電網(wǎng)最優(yōu)孤島劃分模型和算法[D];天津大學(xué);2011年

6 馬婭婕;MPLS網(wǎng)絡(luò)拓?fù)渚酆纤惴ǖ难芯縖D];華中科技大學(xué);2005年

7 趙大勝;無線傳感器網(wǎng)絡(luò)廣播與節(jié)點(diǎn)休眠算法中的節(jié)能覆蓋問題研究[D];華中科技大學(xué);2005年

8 胡鵬;無線自組網(wǎng)路由關(guān)鍵技術(shù)的研究[D];中國科學(xué)技術(shù)大學(xué);2006年

9 張磊;移動(dòng)自組網(wǎng)絡(luò)協(xié)議關(guān)鍵技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2005年

10 汪學(xué)清;無線傳感器網(wǎng)絡(luò)中連通與覆蓋問題研究[D];哈爾濱工程大學(xué);2006年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 劉蘭濤;無線傳感器網(wǎng)絡(luò)中時(shí)間同步技術(shù)的研究[D];鄭州大學(xué);2010年

2 王楠楠;無線網(wǎng)絡(luò)中基于CDS的拓?fù)淇刂扑惴ㄑ芯縖D];曲阜師范大學(xué);2011年

3 朱韜;移動(dòng)Ad hoc網(wǎng)絡(luò)中文件廣播分發(fā)算法的研究與實(shí)現(xiàn)[D];杭州電子科技大學(xué);2011年

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

5 張軍;關(guān)于無線傳感器網(wǎng)絡(luò)虛擬骨干網(wǎng)構(gòu)造算法的研究[D];電子科技大學(xué);2011年

6 王懷彩;基于圖論的移動(dòng)Ad Hoc網(wǎng)絡(luò)分群算法研究[D];青島理工大學(xué);2010年

7 侯加濤;延遲容忍移動(dòng)傳感器網(wǎng)絡(luò)中基于接收者的分階段數(shù)據(jù)傳輸協(xié)議[D];湖南科技大學(xué);2011年

8 韓希先;基于分類樹的P2P電子商務(wù)平臺(tái)搜索機(jī)制的研究[D];哈爾濱工業(yè)大學(xué);2006年

9 李嘉琳;復(fù)雜網(wǎng)絡(luò)核心子網(wǎng)的構(gòu)造及特性分析[D];大連理工大學(xué);2006年

10 王雪瑜;無線傳感器網(wǎng)絡(luò)虛擬骨干網(wǎng)的構(gòu)造研究[D];哈爾濱工業(yè)大學(xué);2006年

，

本文編號(hào)：1210385