WSN中2-連通2-支配集構造算法.pdf

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

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

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

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