【摘要】：隨著網(wǎng)絡(luò)通信技術(shù)的發(fā)展,無線網(wǎng)絡(luò)由于其易安裝,靈活性好和低成本等優(yōu)勢,在保健醫(yī),戰(zhàn)場監(jiān)測,農(nóng)業(yè)和交通控制等領(lǐng)域被廣泛應(yīng)用.無線網(wǎng)絡(luò)中的節(jié)點都是一個個廉價的傳感器,每個傳感器都是由電池供電,其有一定的壽命.為了增加無線網(wǎng)絡(luò)監(jiān)控的生命周期,并防止信息冗余和廣播風(fēng)暴的發(fā)生,許多專家學(xué)者提出改變原有的信息傳遞方式,應(yīng)用虛擬骨干網(wǎng)作為無線網(wǎng)絡(luò)的網(wǎng)絡(luò)基站,即連通支配集.而當一個無線網(wǎng)絡(luò)出現(xiàn)入侵者節(jié)點,如故障點、著火點或破壞節(jié)點等等.入侵節(jié)點的鄰居節(jié)點可能會發(fā)生故障,其可能會傳遞錯誤的信息或不傳遞任何信息,這時候就需要虛擬骨干網(wǎng)具有一定的容錯能力.為解決這一問題,學(xué)者Slater提出了誤報容錯支配集(LR)來增強網(wǎng)絡(luò)的容錯性.本文主要研究一般連通圖(頂點數(shù)超過3)的最小連通誤報容錯支配集的構(gòu)造算法,依次給出了對應(yīng)的多項式模型算法、近似算法、精確算法和啟發(fā)式算法,最后還對精確算法和啟發(fā)式算法進行實現(xiàn)模擬比較,具體內(nèi)容如下.首先證明了最小連通誤報容錯支配集(MCLR)問題屬于NP-hard問題,并給出LR問題的多項式計算模型和CLR的多項式模型算法,多項式模型的時間復(fù)雜性驗證了最小連通誤報容錯支配集問題屬于NP-hard問題.其次,給出了一個在一般連通圖上構(gòu)造最小連通誤報容錯支配集的近似算法,這里的近似算法思想是基于貪婪策略,其近似比為2(1+ln△),其中△是圖中點的最大度,這個近似比優(yōu)于前人的結(jié)果.最后給出了在一般連通圖上的求解最小連通誤報容錯支配集的一個精確算法和一個多項式時間的啟發(fā)式算法,通過計算機仿真,比較兩算法的實驗結(jié)果.
【圖文】：

圖H的構(gòu)造

連通誤報容錯支配集構(gòu)造示例1如圖4.1,圖中包含12個頂點,根據(jù)啟發(fā)式算法,找到圖中點度數(shù)最大的點6號節(jié)點放到支配集中,并且更新L0,這里用紅色表示節(jié)點被選為支配集節(jié)點,藍色表示被1-支配的節(jié)點,灰色表示被2-支配的節(jié)點
【學(xué)位授予單位】：中國計量大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2018
【分類號】：O157.5

【相似文獻】

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

1 駱偉忠;馮啟龍;王建新;陳建二;;完全p-支配集的參數(shù)算法[J];計算機學(xué)報;2013年09期

2 王康;禹繼國;;無線網(wǎng)絡(luò)中一種簡單的弱連通支配集構(gòu)造策略[J];計算機工程與應(yīng)用;2011年20期

3 李鎮(zhèn)堅;葛啟;王海濤;朱洪;;圖的支配集若干問題的研究[J];計算機科學(xué);2007年01期

4 黃民肅;向東;;無線自組網(wǎng)絡(luò)中的基于多個支配集的路由協(xié)議[J];計算機應(yīng)用研究;2007年05期

5 吳迪;梁輝;王光興;;無線自組網(wǎng)簇間網(wǎng)關(guān)支配集優(yōu)化策略[J];計算機工程;2007年24期

6 孫立山;郝燕玲;;能量限制的連通支配集分布式構(gòu)造[J];計算機工程與應(yīng)用;2006年32期

7 蘇岐芳;圖的支配集的有效算法[J];臺州學(xué)院學(xué)報;2003年06期

8 張光鐸，王正志;圖論中獨立支配集的最佳求解算法研究[J];國防科技大學(xué)學(xué)報;1995年02期

9 沈湘鐘;黃友銳;吳建坤;;基于連通支配集的無線傳感器網(wǎng)絡(luò)拓撲控制算法仿真研究[J];儀表技術(shù)與傳感器;2016年09期

10 趙學(xué)鋒;;求解最小連通r-跳k-支配集的啟發(fā)式算法[J];計算機工程;2012年21期

相關(guān)會議論文 前3條

1 李海坡;馬向南;;無線傳感器網(wǎng)絡(luò)中基于連通支配集的覆蓋控制算法[A];中國通信學(xué)會第六屆學(xué)術(shù)年會論文集（下）[C];2009年

2 李克清;;基于定向擴散的最小連通支配集構(gòu)造算法[A];蘇州市自然科學(xué)優(yōu)秀學(xué)術(shù)論文匯編(2008-2009)[C];2010年

3 藍慧琴;鐘誠;李智;;一種改進的基于連通支配集的P2P搜索算法[A];2006年全國開放式分布與并行計算學(xué)術(shù)會議論文集（二）[C];2006年

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

1 袁福宇;若干支配集優(yōu)化問題求解的方法研究[D];東北師范大學(xué);2019年

2 施韋;移動Ad Hoc網(wǎng)絡(luò)中連通支配集若干關(guān)鍵問題的研究[D];浙江大學(xué);2007年

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

4 駱偉忠;無線網(wǎng)絡(luò)中若干NP-難問題的參數(shù)算法[D];中南大學(xué);2012年

5 劉卓;無線傳感器網(wǎng)絡(luò)拓撲建立方法與應(yīng)用技術(shù)研究[D];華中科技大學(xué);2011年

6 陶凱;廣域定向MANET組網(wǎng)關(guān)鍵技術(shù)研究[D];哈爾濱工程大學(xué);2015年

7 鄭瑩;基于樹分解的難解問題的參數(shù)算法研究[D];中南大學(xué);2013年

8 于瑞云;無線傳感器網(wǎng)絡(luò)中面向數(shù)據(jù)采集的支配集算法與策略研究[D];東北大學(xué);2009年

9 張強;基于連通性的無線傳感器網(wǎng)絡(luò)節(jié)點定位技術(shù)研究[D];天津大學(xué);2011年

10 李睿智;基于局部搜索策略的若干組合優(yōu)化問題求解算法研究[D];東北師范大學(xué);2017年

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

1 武舒;無線網(wǎng)絡(luò)中連通支配集問題的算法設(shè)計與分析[D];曲阜師范大學(xué);2019年

2 李有浩;圖的連通誤報容錯支配集算法研究[D];中國計量大學(xué);2018年

3 徐彤;WSN中連通支配集構(gòu)造算法的研究[D];南昌航空大學(xué);2019年

4 齊曉晗;基于多連通支配集調(diào)度機制的飛行自組網(wǎng)拓撲控制算法[D];哈爾濱工業(yè)大學(xué);2018年

5 荊瑩;基于時變連通支配集的多層衛(wèi)星網(wǎng)絡(luò)路由算法[D];哈爾濱工業(yè)大學(xué);2017年

6 劉華麗;若干圖的連通支配問題研究[D];中國計量大學(xué);2017年

7 劉培麗;基于集序的集優(yōu)化問題的穩(wěn)定性及魯棒性分析[D];重慶大學(xué);2018年

8 徐培培;無線傳感網(wǎng)絡(luò)中強連通支配集的構(gòu)造研究[D];南昌航空大學(xué);2016年

9 任思君;最小連通支配集算法研究[D];上海交通大學(xué);2015年

10 魯?shù)窃?無線傳感器網(wǎng)絡(luò)中連通支配集的構(gòu)造算法研究[D];蘇州大學(xué);2014年

，

本文編號：2645361