WSN中2-連通2-支配集構(gòu)造算法.pdf

1、通過(guò)向監(jiān)測(cè)區(qū)域內(nèi)隨機(jī)投放大量多功能的、低成本的、低功耗的微型傳感器節(jié)點(diǎn),各微型傳感器之間以無(wú)線通信的方式連接并構(gòu)建出一個(gè)多跳自組織網(wǎng)絡(luò)系統(tǒng),該網(wǎng)絡(luò)系統(tǒng)即為我們所熟悉的無(wú)線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks, WSN)。能廣泛適用于軍事國(guó)防、交通運(yùn)輸管理、環(huán)境的科學(xué)監(jiān)測(cè)、醫(yī)療保健、智能家居、空間探索等諸多領(lǐng)域。為有效提高傳感器節(jié)點(diǎn)間的信息廣播效率,又避免泛洪(flooding)算法引起的廣播風(fēng)暴,一般通過(guò)在圖論中

2、構(gòu)造連通支配集形成虛擬骨干網(wǎng)來(lái)分層路由。
　　由于采用構(gòu)造連通支配集作為網(wǎng)絡(luò)虛擬骨干網(wǎng),使得節(jié)點(diǎn)信息傳輸大部分在連通支配集中進(jìn)行,導(dǎo)致連通支配集中的節(jié)點(diǎn)可能因能量耗盡失效。另外無(wú)線傳感器網(wǎng)絡(luò)自身的不穩(wěn)定性特點(diǎn)決定了節(jié)點(diǎn)和鏈路失效經(jīng)常發(fā)生,因此必須考慮它的容錯(cuò)能力。構(gòu)造一個(gè)容錯(cuò)性好的連通支配集使其盡可能減少網(wǎng)絡(luò)開銷,并在某些支配節(jié)點(diǎn)失效或鏈路失敗時(shí)仍能正常工作以延長(zhǎng)網(wǎng)絡(luò)生命周期,是一個(gè)很重要的研究課題。
　　本文主要借助虛擬骨

3、干網(wǎng)理論,研究無(wú)線傳感器網(wǎng)絡(luò)中連通支配集的算法構(gòu)造,并將研究問題抽象為研究簡(jiǎn)單無(wú)向圖中連通支配集問題。如何在簡(jiǎn)單圖中構(gòu)造最小連通支配集(Minimum CDS,MCDS)已然公認(rèn)是NP完全問題,一般只能采取求解近似值。本文通過(guò)綜合研究節(jié)點(diǎn)度、節(jié)點(diǎn)剩余能量、能量閾值等因素對(duì)構(gòu)造容錯(cuò)連通支配集的影響,提出一種能量均衡的最小2-連通2-支配集的分布式算法(DA-EBM)。首先通過(guò)研究影響生命周期的各個(gè)因素,主要分析支配節(jié)點(diǎn)度與理想支配節(jié)點(diǎn)數(shù)目

4、之間、節(jié)點(diǎn)剩余能量與能量閾值之間的關(guān)系,并綜合考慮剩余能量和節(jié)點(diǎn)度等因素的權(quán)值公式作為支配點(diǎn)選取的最佳選取策略。其次,算法DA-EBM主要分為容錯(cuò)連通支配集的構(gòu)造階段和冗余優(yōu)化階段兩部分進(jìn)行描述,通過(guò)盡可能的選取節(jié)點(diǎn)度接近理想支配度以及節(jié)點(diǎn)能量高于閾值的節(jié)點(diǎn)作為支配點(diǎn),進(jìn)一步優(yōu)化冗余從而得到能量均衡的最小2-連通2-支配集。
　　通過(guò)算法仿真實(shí)驗(yàn)及相關(guān)性能分析表明,DA-EBM算法綜合考慮剩余能量和節(jié)點(diǎn)度等因素,采用權(quán)值公式所構(gòu)造