發(fā)布時(shí)間：2017-08-05 14:09

  本文關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)中兩類覆蓋問題的算法研究

  更多相關(guān)文章： 無線傳感器網(wǎng)絡(luò) 覆蓋問題 NP-困難 近似算法 性能比

【摘要】：無線傳感器網(wǎng)絡(luò)作為一種全新的信息獲取和處理技術(shù),能夠廣泛應(yīng)用在反恐抗災(zāi)、國(guó)防軍事、醫(yī)療衛(wèi)生以及環(huán)境監(jiān)測(cè)等諸多領(lǐng)域,被認(rèn)為是二十一世紀(jì)最重要的技術(shù)之一。目標(biāo)覆蓋問題是傳感器網(wǎng)絡(luò)進(jìn)行目標(biāo)識(shí)別、監(jiān)控、跟蹤等眾多應(yīng)用的前提,也是無線傳感器網(wǎng)絡(luò)研究中的熱點(diǎn)問題之一�，F(xiàn)有的目標(biāo)覆蓋類型大致可分為三類:點(diǎn)覆蓋、線覆蓋以及區(qū)域覆蓋。本文重點(diǎn)研究點(diǎn)覆蓋和線段覆蓋兩類問題,論文結(jié)構(gòu)主要包括以下三大部分。第一部分,預(yù)備知識(shí)介紹和問題引入。該部分給出了圖論、組合優(yōu)化、計(jì)算復(fù)雜性、近似算法等相關(guān)定義,并介紹了無線傳感器網(wǎng)絡(luò)中覆蓋問題的背景、應(yīng)用、發(fā)展歷程以及國(guó)內(nèi)外相關(guān)研究成果。第二部分,論文主要內(nèi)容:對(duì)無線傳感器網(wǎng)絡(luò)中的線段覆蓋和點(diǎn)覆蓋兩類問題進(jìn)行研究。第一類問題——線段覆蓋問題,我們重點(diǎn)考慮目標(biāo)線段處于水平放置或者豎直放置的情形。首先,討論最大線段長(zhǎng)度不超過傳感器感應(yīng)半徑兩倍的特殊情形,由于該問題是NP-困難的,我們主要從近似算法的角度來求解問題:利用平面分割的思想,設(shè)計(jì)了一個(gè)性能比為18、時(shí)間復(fù)雜度為O(nlog n)(n為線段數(shù)量)的多項(xiàng)式時(shí)間近似算法。其次,利用Java語言編程完成了算法仿真和穩(wěn)定性檢驗(yàn),以圖像形式形象地展示了算法結(jié)果,多組數(shù)據(jù)顯示該算法基本穩(wěn)定。最后,對(duì)該問題的一般情形進(jìn)行了初步探討。第二類問題——點(diǎn)覆蓋問題,重點(diǎn)考慮傳感器部署位置不能越過某一條直線的情形(受地理環(huán)境或者其他因素的影響,傳感器的部署位置可能存在一些禁區(qū))。由于該問題也是NP-困難的,我們?cè)O(shè)計(jì)了一個(gè)性能比為2、時(shí)間復(fù)雜度為O(n~2)(n為點(diǎn)的數(shù)量)的多項(xiàng)式時(shí)間近似算法,且有實(shí)例表明該性能比是緊的。同樣地,該部分也利用Java語言編程完成了算法仿真和穩(wěn)定性檢驗(yàn),得到了多組算法解與最優(yōu)解的圖像示例,計(jì)算結(jié)果表明該算法也較為穩(wěn)定。第三部分,論文的總結(jié)和拓展。最后對(duì)論文主要內(nèi)容作了總結(jié),并展望進(jìn)一步的研究方向。
【關(guān)鍵詞】：無線傳感器網(wǎng)絡(luò) 覆蓋問題 NP-困難 近似算法 性能比
【學(xué)位授予單位】：杭州電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：TP212.9;TN929.5
【目錄】：

• 摘要5-6
• ABSTRACT6-9
• 1 緒論9-13
• 1.1 圖論的相關(guān)概念9
• 1.2 組合優(yōu)化問題9-10
• 1.2.1 問題和實(shí)例9-10
• 1.2.2 數(shù)學(xué)模型和組合優(yōu)化問題10
• 1.3 算法與時(shí)間復(fù)雜性10
• 1.4 問題復(fù)雜性分類10-11
• 1.4.1 優(yōu)化問題的判定形式10-11
• 1.4.2 多項(xiàng)式問題類(P)11
• 1.4.3 非確定多項(xiàng)式問題類(NP)11
• 1.4.4 NP完全問題類(NPC)11
• 1.5 近似算法和啟發(fā)式算法11-12
• 1.5.1 近似算法12
• 1.5.2 啟發(fā)式算法12
• 1.6 論文的組織結(jié)構(gòu)12-13
• 2 無線傳感器網(wǎng)絡(luò)的相關(guān)介紹13-18
• 2.1 無線傳感器網(wǎng)絡(luò)13-15
• 2.1.1 無線傳感器網(wǎng)絡(luò)的基本概念13
• 2.1.2 無線傳感器網(wǎng)絡(luò)的應(yīng)用背景13-14
• 2.1.3 無線傳感器網(wǎng)絡(luò)的發(fā)展歷程14-15
• 2.2 無線傳感器網(wǎng)絡(luò)中的覆蓋問題15-18
• 2.2.1 覆蓋問題的相關(guān)定義15
• 2.2.2 覆蓋問題的相關(guān)研究15-18
• 3 無線傳感器網(wǎng)絡(luò)中線段覆蓋問題的算法研究18-24
• 3.1 問題描述18
• 3.2 算法設(shè)計(jì)與分析18-20
• 3.2.1 算法設(shè)計(jì)18-19
• 3.2.2 性能比分析19-20
• 3.3 算法仿真和穩(wěn)定性檢驗(yàn)20-23
• 3.4 問題延伸23
• 3.5 本章小結(jié)23-24
• 4 無線網(wǎng)絡(luò)中點(diǎn)覆蓋問題的算法研究24-29
• 4.1 問題描述24
• 4.2 算法設(shè)計(jì)與分析24-26
• 4.2.1 算法設(shè)計(jì)24
• 4.2.2 算法示例24-25
• 4.2.3 性能比分析25-26
• 4.3 算法仿真和穩(wěn)定性檢驗(yàn)26-28
• 4.4 本章小結(jié)28-29
• 5 總結(jié)與展望29-30
• 5.1 總結(jié)29
• 5.2 問題展望29-30
• 5.2.1 算法優(yōu)化29
• 5.2.2 問題拓展29-30
• 致謝30-31
• 參考文獻(xiàn)31-34
• 附錄 1--線段覆蓋算法的主要程序代碼34-38
• 附錄 2--點(diǎn)覆蓋算法的主要程序代碼38-40
• 附錄 3 作者在讀期間完成的學(xué)術(shù)論文及參加的科研項(xiàng)目40

【相似文獻(xiàn)】

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

1 夏俐,陳曦,趙千川,江永亨,管曉宏;無線傳感器網(wǎng)絡(luò)及應(yīng)用簡(jiǎn)介[J];自動(dòng)化博覽;2004年01期

2 孫雨耕,張靜,孫永進(jìn),房朝暉;無線自組傳感器網(wǎng)絡(luò)[J];傳感技術(shù)學(xué)報(bào);2004年02期

3 夏俐;陳曦;趙千川;江永亨;管曉宏;;無線傳感器網(wǎng)絡(luò)及應(yīng)用簡(jiǎn)介[J];自動(dòng)化博覽;2005年S2期

4 莊慶德;傳感器網(wǎng)絡(luò)的研究現(xiàn)狀[J];國(guó)外電子測(cè)量技術(shù);2005年04期

5 謝潔銳;胡月明;劉才興;劉蘭;;大田監(jiān)測(cè)中無線傳感器網(wǎng)絡(luò)的部署[J];現(xiàn)代計(jì)算機(jī);2006年03期

6 李小遐;劉瑞霞;;一種無線傳感器網(wǎng)絡(luò)的設(shè)計(jì)[J];自動(dòng)化技術(shù)與應(yīng)用;2006年04期

7 吳春婧;鄭明春;秦繼林;;無線傳感器網(wǎng)絡(luò)協(xié)議研究[J];計(jì)算機(jī)技術(shù)與發(fā)展;2006年08期

8 徐勇軍;楊宇;;無線傳感器網(wǎng)絡(luò)的發(fā)展[J];電子產(chǎn)品世界;2006年19期

9 ;堅(jiān)固的無線傳感器網(wǎng)絡(luò)適合苛刻的工業(yè)環(huán)境[J];電子設(shè)計(jì)技術(shù);2006年09期

10 馬華東;陶丹;;多媒體傳感器網(wǎng)絡(luò)及其研究進(jìn)展[J];軟件學(xué)報(bào);2006年09期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫 前10條

1 彭政;魏巍;羅相根;羅永健;;無線傳感器網(wǎng)絡(luò)中傳感器數(shù)量的選擇方法[A];第十九屆測(cè)控、計(jì)量、儀器儀表學(xué)術(shù)年會(huì)(MCMI'2009)論文集[C];2009年

2 程時(shí)端;;傳感器網(wǎng)絡(luò)[A];中國(guó)通信學(xué)會(huì)信息通信網(wǎng)絡(luò)技術(shù)委員會(huì)2004年年會(huì)論文集[C];2004年

3 楊曼;;無線傳感器網(wǎng)絡(luò)對(duì)抗[A];四川省電子學(xué)會(huì)情報(bào)專業(yè)委員會(huì)學(xué)術(shù)交流會(huì)論文集[C];2006年

4 闞鳳龍;徐自文;陳楠;左傳文;;無線傳感器網(wǎng)絡(luò)的應(yīng)用及其發(fā)展研究[A];第九屆沈陽科學(xué)學(xué)術(shù)年會(huì)論文集（信息科學(xué)與工程技術(shù)分冊(cè)）[C];2012年

5 賈杰;趙林亮;常桂然;;面向異構(gòu)傳感器網(wǎng)絡(luò)的高能效覆蓋控制[A];中國(guó)通信學(xué)會(huì)第六屆學(xué)術(shù)年會(huì)論文集（下）[C];2009年

6 馮健昭;肖德琴;肖克輝;李就好;;基于謂詞的水質(zhì)傳感器網(wǎng)絡(luò)采樣整合優(yōu)化算法[A];紀(jì)念中國(guó)農(nóng)業(yè)工程學(xué)會(huì)成立30周年暨中國(guó)農(nóng)業(yè)工程學(xué)會(huì)2009年學(xué)術(shù)年會(huì)（CSAE 2009）論文集[C];2009年

7 唐云龍;;無線傳感器網(wǎng)絡(luò)系統(tǒng)實(shí)驗(yàn)分析[A];工程設(shè)計(jì)與計(jì)算機(jī)技術(shù)：第十五屆全國(guó)工程設(shè)計(jì)計(jì)算機(jī)應(yīng)用學(xué)術(shù)會(huì)議論文集[C];2010年

8 杜景林;陳力軍;謝立;;無線傳感器網(wǎng)絡(luò)與互聯(lián)網(wǎng)集成體系結(jié)構(gòu)[A];2008年全國(guó)開放式分布與并行計(jì)算機(jī)學(xué)術(shù)會(huì)議論文集(下冊(cè))[C];2008年

9 李新;田斌;辛陽;陳林順;;傳感器網(wǎng)絡(luò)中基于音頻的異常事件檢測(cè)方法[A];中國(guó)電子學(xué)會(huì)第十七屆信息論學(xué)術(shù)年會(huì)論文集[C];2010年

10 劉昊;;面向電子智能服裝的人體無線傳感器網(wǎng)絡(luò)構(gòu)建[A];“力恒杯”第11屆功能性紡織品、納米技術(shù)應(yīng)用及低碳紡織研討會(huì)論文集[C];2011年

中國(guó)重要報(bào)紙全文數(shù)據(jù)庫 前10條

1 羅清岳;讓無線傳感器網(wǎng)絡(luò)走入生活[N];電子資訊時(shí)報(bào);2007年

2 ;多媒體傳感器網(wǎng)絡(luò)[N];中國(guó)計(jì)算機(jī)報(bào);2006年

3 美國(guó)專利律師 譚文曄　薛之揚(yáng);無線傳感器網(wǎng)絡(luò)技術(shù)專利分析[N];科技日?qǐng)?bào);2010年

4 本報(bào)記者 趙建國(guó);無線傳感器網(wǎng)絡(luò)改變未來世界[N];中國(guó)知識(shí)產(chǎn)權(quán)報(bào);2011年

5 樊哲高;我國(guó)傳感器網(wǎng)絡(luò)標(biāo)準(zhǔn)工作取得新進(jìn)展[N];中國(guó)電子報(bào);2012年

6 本報(bào)記者 王博;傳感器網(wǎng)絡(luò)標(biāo)準(zhǔn)取得新進(jìn)展[N];計(jì)算機(jī)世界;2012年

7 溫雅路;利用無線傳感器網(wǎng)絡(luò)提高地質(zhì)災(zāi)害監(jiān)測(cè)能力[N];人民郵電;2008年

8 林宗輝;ZigBee無線傳感器網(wǎng)絡(luò)解決方案[N];電子資訊時(shí)報(bào);2007年

9 賽迪顧問信息產(chǎn)業(yè)研究中心高級(jí)咨詢師 王坤;國(guó)內(nèi)外物聯(lián)網(wǎng)技術(shù)研究進(jìn)展[N];通信產(chǎn)業(yè)報(bào);2009年

10 本報(bào)記者 張彤;物物之連[N];網(wǎng)絡(luò)世界;2010年

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

1 馬瑞;基于小生境粒子群算法的機(jī)艙WSN目標(biāo)覆蓋研究[D];大連海事大學(xué);2014年

2 李洪峻;面向入侵目標(biāo)追捕的多回路無線網(wǎng)絡(luò)控制系統(tǒng)設(shè)計(jì)與相關(guān)技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2013年

3 張德敬;基于虛擬坐標(biāo)的無線傳感器網(wǎng)絡(luò)路由協(xié)議研究[D];山東大學(xué);2015年

4 楊顯輝;森林資源數(shù)據(jù)獲取的移動(dòng)Sink無線傳感器網(wǎng)絡(luò)可靠性研究[D];東北林業(yè)大學(xué);2015年

5 畢冉;基于無線傳感器網(wǎng)絡(luò)的事件監(jiān)測(cè)算法研究[D];哈爾濱工業(yè)大學(xué);2015年

6 石熙;數(shù)字水印技術(shù)在無線傳感器網(wǎng)絡(luò)安全中的應(yīng)用研究[D];重慶大學(xué);2015年

7 徐力杰;低占空比傳感器網(wǎng)絡(luò)的數(shù)據(jù)傳輸調(diào)度問題研究[D];南京大學(xué);2014年

8 歐陽鍵;面向無線傳感器網(wǎng)絡(luò)的協(xié)作傳輸技術(shù)研究[D];南京航空航天大學(xué);2014年

9 馮森;面向智能配用電的無線傳感器網(wǎng)絡(luò)路由優(yōu)化協(xié)議研究[D];華北電力大學(xué);2015年

10 徐毅;無線傳感器網(wǎng)絡(luò)低能耗路由協(xié)議研究[D];山東大學(xué);2015年

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

1 胥常杰;傳感器網(wǎng)絡(luò)設(shè)計(jì)的數(shù)學(xué)模型及其應(yīng)用[D];青島大學(xué);2010年

2 黃錚;無線傳感器網(wǎng)絡(luò)連通與覆蓋的研究[D];武漢理工大學(xué);2006年

3 馬艷麗;基于無線傳感器網(wǎng)絡(luò)的瓦斯監(jiān)測(cè)系統(tǒng)的定位技術(shù)的研究[D];燕山大學(xué);2015年

4 吳旭東;基于ZigBee無線傳感器網(wǎng)絡(luò)的電表監(jiān)控系統(tǒng)的設(shè)計(jì)實(shí)現(xiàn)[D];西南交通大學(xué);2015年

5 劉其永;無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)間通信的信道均衡研究[D];海南大學(xué);2015年

6 王慧彬;無線傳感器網(wǎng)絡(luò)拓?fù)鋬?yōu)化以及容錯(cuò)控制算法研究[D];燕山大學(xué);2015年

7 王龍;無線傳感器網(wǎng)絡(luò)覆蓋空洞檢測(cè)算法研究[D];燕山大學(xué);2015年

8 劉晨;基于粒子群優(yōu)化的無線傳感器網(wǎng)絡(luò)定位算法研究[D];昆明理工大學(xué);2015年

9 侯文蕾;無線傳感器移動(dòng)節(jié)點(diǎn)在WSN中的定位研究[D];昆明理工大學(xué);2015年

10 孫超;能量?jī)?yōu)化的無線傳感器網(wǎng)絡(luò)分布式濾波與融合[D];昆明理工大學(xué);2015年

，

本文編號(hào)：625271