【摘要】：由于無線傳感器網(wǎng)絡(Wireless Sensor Network,WSN)具有低功耗、自組織、多跳等特點,因此被廣泛應用于諸多領域,如醫(yī)療衛(wèi)生、國防軍事、環(huán)境監(jiān)測等。目前,WSN已引起研究人員的高度關注。其中,虛擬骨干網(wǎng)已成為該領域的熱門研究之一,它在網(wǎng)絡中的主要作用是進行路由管理。利用圖論中的連通支配集(Connected Dominating Set,CDS)在WSN中構建虛擬骨干網(wǎng)以構造分層網(wǎng)絡的方法已被普遍運用。然而WSN中的節(jié)點具有能量不足以及處理和儲存能力低等缺陷,因此如何均衡利用節(jié)點能量從而盡可能延長網(wǎng)絡的生命周期成為研究的重點。本文通過對已有連通支配集構造算法的研究以及總結歸納,首先提出一種基于能量均衡改進的集中式算法(Centralized Algorithm for Improved Energy-Balance Connected Dominating Set,IEB-CDS)構造連通支配集,綜合考慮節(jié)點的一跳和二跳鄰居節(jié)點,剩余能量及能量閾值等影響虛擬骨干網(wǎng)網(wǎng)絡周期的因素,構造節(jié)點權值公式。IEB-CDS算法分三個階段實現(xiàn)。第一階段選取具有較大權值的節(jié)點以構造一個獨立集,第二階段選取權值較大的節(jié)點連接獨立集中的節(jié)點,第三階段檢查網(wǎng)絡中是否所有節(jié)點都被支配。通過仿真實驗及相關分析表明,IEB-CDS算法不僅能獲得較小的連通支配集,而且可以有效地均衡整個網(wǎng)絡的節(jié)點能量,延長了網(wǎng)絡壽命。以上提出的算法是在無向圖中進行研究的,每個節(jié)點均有相同的傳輸范圍,然而在實際網(wǎng)絡情況中,由于功率和功能的差異,大多數(shù)網(wǎng)絡鏈路是不對稱的,網(wǎng)絡中各節(jié)點的通信范圍不一定相同。針對這一問題,本文在IBE-CDS的基礎上提出了一種基于有向圖的強連通支配集構造算法D-SCDS(Construction Algorithm of Strongly Connected Dominating Set based on Directed graphs)。首先分析影響網(wǎng)絡生命周期的各個因素,D-SCDS算法考慮全局網(wǎng)絡信息,利用權值公式計算節(jié)點權值,選取權值較大的節(jié)點構造強連通支配集。通過仿真實驗及相關對比分析表明,D-SCDS算法最終得到一個能量均衡,規(guī)模較小以及生命周期較長的強連通支配集。
【學位授予單位】：南昌航空大學
【學位級別】：碩士
【學位授予年份】：2019
【分類號】：TP212.9;TN929.5
【圖文】：

同時也為數(shù)據(jù)轉發(fā)和避免路由協(xié)議中的故障節(jié)點提供了基礎。近年來，相關學者將“虛擬骨干網(wǎng)”（如圖1-1）的概念應用于 WSN，通過虛擬骨干網(wǎng)進行層次拓撲結構的研究。基于虛擬骨干網(wǎng)的拓撲結構不僅可以盡快適應網(wǎng)絡拓撲的變化，還可以應用于網(wǎng)絡節(jié)點的路由過程[8]。通常，研究人員使用圖論中的連通支配集（Connected Dominating Set，

的相關概念基于圖（Graph），是數(shù)學的一個分支[58]。圖由很多給定的點以及點之成，普遍用于表示事物間的某種關系。其中，點表示事物，點之間的線之間存在的關系。WSN 可以抽象成圖來表示，圖中的頂點對應 WSN 的點間的邊對應 WSN 中各節(jié)點間的通信鏈路。因此，利用圖的基本性質SN 的拓撲結構進行深入研究，從而優(yōu)化網(wǎng)絡性能�；径x頂點集和頂點間的邊集組成，一般用 G (V ,E)來表示。其中， nV v,v...,v12, 集，稱 V 中的元素為頂點，n=|V|表示頂點的個數(shù)。 mE e,e,...,e12 表示 E 中的元素為邊，m=|E|表示邊數(shù)。實踐中，網(wǎng)絡拓撲圖通常由幾何圖由平面上的點表示圖中的頂點，頂點之間的連線表示邊。如果圖形的所有方向，則該圖形稱為為無向圖。否則，稱為有向圖。如下圖 2-1 所示

稱這種圖為簡單無向圖。通圖）：對于無向圖 G (V ,E)，若 v, vij 連通圖。通圖）：若 G (V ,E)是有向圖，對于 v i jv 。當存在ijv v或j viv 時，稱 G 為j viv ，則稱 G 為強連通有向圖。設置一個集合I ， I V，對于 vVij v , G 的一個獨立集（Independent Set，I不再是 IS，則稱I 為 G 的極大獨立集(M 中最大頂點數(shù)的 IS 為最大獨立集， （G）表示，簡單表示為 。如圖 2-2 的研究中，可以利用極大獨立集來構

【相似文獻】

相關期刊論文 前10條

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

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

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

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

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

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

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

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

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

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

相關會議論文 前3條

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

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

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

相關博士學位論文 前10條

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

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

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

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

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

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

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

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

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

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

相關碩士學位論文 前10條

1 徐彤;WSN中連通支配集構造算法的研究[D];南昌航空大學;2019年

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

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

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

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

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

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

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

9 林霖;無線傳感器網(wǎng)絡分布式連通支配集構造方法研究[D];電子科技大學;2012年

10 陳蓓瑋;加權邊支配集問題的參數(shù)算法研究[D];中南大學;2009年

本文編號：2782709