本文關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)中虛擬骨干網(wǎng)構(gòu)造算法研究

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

【摘要】：本文主要研究無線傳感器網(wǎng)絡(luò)中的虛擬骨干網(wǎng)構(gòu)建所產(chǎn)生的相關(guān)組合優(yōu)化問題。由于其廣泛的應(yīng)用性,無線傳感器網(wǎng)絡(luò)(WSN)近十幾年來得到了深入研究。它是一個沒有基礎(chǔ)設(shè)施的自組織無線移動網(wǎng)絡(luò),并且傳感器網(wǎng)絡(luò)中的節(jié)點很容易發(fā)生故障或者能量耗盡導(dǎo)致通信中斷,因此提出了在網(wǎng)絡(luò)中構(gòu)建虛擬骨干網(wǎng)來負(fù)責(zé)數(shù)據(jù)的路由轉(zhuǎn)發(fā)。虛擬骨干網(wǎng)作為路由協(xié)議可以很好的解決由泛洪帶來的廣播風(fēng)暴,從而減少大量的冗余信息,減少節(jié)點通信時的能耗,進(jìn)而改善網(wǎng)絡(luò)性能。 本文研究的主要內(nèi)容包括兩個方面。首先,我們針對無向圓盤圖中的最小m-連通k-全控制集問題(其中,m,k為任意正整數(shù)),提出了一個近似算法,對此算法進(jìn)行了理論分析,得到一個較好的近似比。其次,我們研究了無向圓盤圖中最小r-跳k-控制集問題(其中,k,r為任意正整數(shù)),給出一個兩階段的近似算法。第一階段,利用三色算法得到一個極大r-跳獨立集；第二階段向控制集加入節(jié)點使得滿足連通性要求,從而得到連通控制集,最后通過對算法的分析得到了近似比。 本文的主要貢獻(xiàn)是推廣了相關(guān)的虛擬骨干網(wǎng)優(yōu)化構(gòu)造問題,并設(shè)計了這些問題的近似算法,得到了較好的近似比。
【關(guān)鍵詞】：無線傳感器網(wǎng)絡(luò) 圓盤圖 最小m-連通k-全控制集 最小r-跳k-控制
【學(xué)位授予單位】：北京郵電大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TP212.9;TN929.5;O157.5
【目錄】：

• 摘要4-6
• ABSTRACT6-8
• 目錄8-9
• 第一章 緒論9-14
• 1.1 研究背景9
• 1.2 體系結(jié)構(gòu)9-10
• 1.3 無線虛擬骨干網(wǎng)絡(luò)的研究意義10-12
• 1.4 相關(guān)工作12
• 1.5 論文結(jié)構(gòu)12-14
• 第二章 基本知識14-20
• 2.1 圖論中的術(shù)語14-15
• 2.2 連通控制集15-16
• 2.2.1 控制集15-16
• 2.2.2 m-連通k-控制集16
• 2.2.3 k-全控制集16
• 2.3 常見算法構(gòu)造的基本思想16-18
• 2.3.1 先控制再連通17
• 2.3.2 先形成回路再構(gòu)造控制17
• 2.3.3 基于概率的算法17-18
• 2.4 網(wǎng)絡(luò)模型18-20
• 2.4.1 單位圓盤圖18-19
• 2.4.2 無向圓盤圖19-20
• 第三章 最小m-連通k-全控制集問題算法設(shè)計與分析20-27
• 3.1 引言20
• 3.2 算法設(shè)計與分析20-25
• 3.2.1 1-連通k-全控制集的近似算法21-23
• 3.2.2 m-連通k-全控制集的近似算法23-25
• 3.3 算法的性能分析25-27
• 第四章 最小r-跳k-控制集問題的近似算法27-46
• 4.1 引言27
• 4.2 算法設(shè)計27-30
• 4.2.1 極大r跳獨立集算法28-29
• 4.2.2 連通r-跳k-控制集算法29-30
• 4.3 算法的性能分析30-46
• 第五章 總結(jié)與展望46-47
• 參考文獻(xiàn)47-50
• 致謝50-51
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文目錄51

【參考文獻(xiàn)】

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

1 帥天平;李業(yè)芳;艾文寶;;傳感器網(wǎng)絡(luò)中最小k-連通m-控制集問題的近似算法[J];工程數(shù)學(xué)學(xué)報;2012年05期

，

本文編號：875127