發(fā)布時(shí)間：2020-08-06 17:04

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

同時(shí)也為數(shù)據(jù)轉(zhuǎn)發(fā)和避免路由協(xié)議中的故障節(jié)點(diǎn)提供了基礎(chǔ)。近年來(lái)，相關(guān)學(xué)者將“虛擬骨干網(wǎng)”（如圖1-1）的概念應(yīng)用于 WSN，通過(guò)虛擬骨干網(wǎng)進(jìn)行層次拓?fù)浣Y(jié)構(gòu)的研究�；谔摂M骨干網(wǎng)的拓?fù)浣Y(jié)構(gòu)不僅可以盡快適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓�可以應(yīng)用于網(wǎng)絡(luò)節(jié)點(diǎn)的路由過(guò)程[8]。通常，研究人員使用圖論中的連通支配集（Connected Dominating Set，

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

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

【相似文獻(xiàn)】

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

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

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

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

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

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

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

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

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

9 沈湘鐘;黃友銳;吳建坤;;基于連通支配集的無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǚ抡嫜芯縖J];儀表技術(shù)與傳感器;2016年09期

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 齊曉晗;基于多連通支配集調(diào)度機(jī)制的飛行自組網(wǎng)拓?fù)淇刂扑惴╗D];哈爾濱工業(yè)大學(xué);2018年

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

4 劉華麗;若干圖的連通支配問(wèn)題研究[D];中國(guó)計(jì)量大學(xué);2017年

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

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

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

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

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

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

本文編號(hào)：2782709