資源描述:
《無(wú)線傳感器網(wǎng)絡(luò)中覆蓋與連通算法的研究》由會(huì)員上傳分享,免費(fèi)在線閱讀,更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、湖南大學(xué)碩士學(xué)位論文無(wú)線傳感器網(wǎng)絡(luò)中覆蓋與連通算法的研究姓名:杜輝申請(qǐng)學(xué)位級(jí)別:碩士專(zhuān)業(yè):計(jì)算機(jī)軟件與理論指導(dǎo)教師:肖德貴20070319碩士學(xué)位論文摘要近年來(lái),集成了傳感器技術(shù)、微電子技術(shù)和無(wú)線通信技術(shù)的無(wú)線傳感器網(wǎng)絡(luò)已引起各國(guó)政府、研究機(jī)構(gòu)和企業(yè)的高度關(guān)注,它在軍事、環(huán)境科學(xué)、醫(yī)療健康和其他商業(yè)領(lǐng)域都有著廣闊的應(yīng)用前景。無(wú)線傳感器網(wǎng)絡(luò)發(fā)展至今,仍有許多可以應(yīng)用的環(huán)境待開(kāi)發(fā),也仍有許多技術(shù)上的問(wèn)題需要克服,值得各界學(xué)者及研究團(tuán)隊(duì)繼續(xù)深入地研究。連通與覆蓋是無(wú)線傳感器網(wǎng)絡(luò)的兩個(gè)最基本的問(wèn)題。覆蓋是指利用網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)對(duì)整個(gè)目標(biāo)區(qū)域進(jìn)行監(jiān)測(cè),從
2、而達(dá)到信息采集的目的。為了反映無(wú)線傳感器網(wǎng)絡(luò)覆蓋的質(zhì)量,覆蓋度通常是評(píng)價(jià)網(wǎng)絡(luò)覆蓋能力的QOS指標(biāo)之一。通過(guò)引入節(jié)點(diǎn)“覆蓋模板”的概念,本文提出一種覆蓋模板掃描算法CTS(CoverageTemplateScan)求解無(wú)線傳感器網(wǎng)絡(luò)覆蓋度,并克服傳統(tǒng)算法中可變的節(jié)點(diǎn)感知半徑以及節(jié)點(diǎn)覆蓋圓邊界效應(yīng)的影響,更好地滿足實(shí)際應(yīng)用需求。無(wú)線傳感器網(wǎng)絡(luò)中,為節(jié)約能耗僅將高密度隨機(jī)分布的傳感器節(jié)點(diǎn)中盡可能少的節(jié)點(diǎn)投入活躍工作狀態(tài)。如何求解能覆蓋整個(gè)目標(biāo)區(qū)域且工作節(jié)點(diǎn)個(gè)數(shù)最少的節(jié)點(diǎn)集合,是一個(gè)NP難問(wèn)題。本文設(shè)計(jì)了一種基于遺傳算法求解最小覆蓋集的優(yōu)化算法,求解覆蓋
3、整個(gè)目標(biāo)區(qū)域的最小節(jié)點(diǎn)覆蓋集。仿真結(jié)果表明,算法能在節(jié)點(diǎn)數(shù)量和有效覆蓋率中做出合理權(quán)衡,得到更適應(yīng)實(shí)際應(yīng)用要求的最小覆蓋集。無(wú)線傳感器網(wǎng)絡(luò)的連通是指網(wǎng)絡(luò)中任意兩個(gè)節(jié)點(diǎn)之間都能夠進(jìn)行通信,這是節(jié)點(diǎn)自組織形成網(wǎng)絡(luò)的前提。通過(guò)分析連通與覆蓋之間的關(guān)系,文中給出了覆蓋意味著連通的充分必要條件。當(dāng)節(jié)點(diǎn)通信半徑大于等于2倍感知半徑時(shí),由遺傳算法構(gòu)造的最小節(jié)點(diǎn)覆蓋集是連通的;當(dāng)節(jié)點(diǎn)通信半徑小于2倍感知半徑時(shí),引入一種基于最小生成樹(shù)(minimumspanningtree,簡(jiǎn)稱MST)的連通算法來(lái)計(jì)算確保遺傳算法構(gòu)造的最小節(jié)點(diǎn)覆蓋集連通所需的輔助節(jié)點(diǎn),保證網(wǎng)絡(luò)對(duì)
4、監(jiān)視區(qū)域的覆蓋與連通。通過(guò)上述對(duì)覆蓋與連通問(wèn)題的研究,最終可以得到覆蓋整個(gè)目標(biāo)區(qū)域且節(jié)點(diǎn)相互連通的最小連通覆蓋集(MCCS)。關(guān)鍵詞:無(wú)線傳感器網(wǎng)絡(luò);遺傳算法;覆蓋度;最小連通覆蓋集I無(wú)線傳感器網(wǎng)絡(luò)中覆蓋與連通算法的研究AbstractRecenttechnologicaladvancesinmicro-electro-mechanicalsystems(MEMS)technology,wirelesscommunications,anddigitalelectronicshaveledtotheemergenceoflarge-scalesen
5、sornetworks.Ithasbeenpredictedtohaveawiderangeofapplicationsrelatedtonationalsecurity,military,environment,healthcare,homeandothercommercialareas.Manyresearchersarecurrentlyengagedindevelopingthetechnologiesneededfordifferentlayersofthesensornetworks.Twoofthemostfundamentalpr
6、oblemsinWSNareconnectivityandcoverage.Coveragemeansthatoverallareashouldbesensedbyallnodessothattheobservercanobtainthewholeinformation.Inthepaper,wecomputerthecoveragedegreeinthewirelesssensornetwork,andproposetheCTS(CoverageTemplateScan)algorithmbyintroducingtheconceptofCov
7、erageTemplate.TheCTSalgorithmtakesfullattentiontoboththedifferentsensingrangeofnodesandtheboundaryeffectofthecoveragerange,soitnotonlysolvesthekcoverageproblem,butalsostrengthenstheadaptationoftheactualapplication.Oneeffectiveapproachtoconservingsystemenergyinwirelesssensorne
8、tworksistokeeponlyaminimalnumberofsensorsactive.Theproblemofcomputin