[發(fā)明專利]無線傳感網(wǎng)中基于隨機(jī)行走的容錯方法

有效

• 申請?zhí)枺?/td>: 201010176659.4
• 申請日: 2010-05-19
• 公開（公告）號: CN102256268A
• 公開（公告）日: 2011-11-23
• 發(fā)明（設(shè)計）人: 白云飛
• 申請（專利權(quán)）人: 北京興科迪科技有限公司
• 主分類號: H04W16/18
• 分類號: H04W16/18;H04W28/04;H04W40/02;H04W84/18
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及無線傳感器網(wǎng)絡(luò)技術(shù)，特別涉及一種無線傳感網(wǎng)中基于隨機(jī)行走的容錯方法。

背景技術(shù)

無線傳感器網(wǎng)絡(luò)是由大量無處不在的、具有無線通信與計算能力的微小傳感器節(jié)點構(gòu)成的自組織分布式網(wǎng)絡(luò)系統(tǒng)。通信技術(shù)的發(fā)展使人們不再滿足于單個傳感器獨立的對環(huán)境進(jìn)行感知，而是希望通過傳感器之間的相互協(xié)作與通信完成更為廣泛與精細(xì)的監(jiān)測任務(wù)，并且把監(jiān)測的數(shù)據(jù)以及部分處理的結(jié)果通過網(wǎng)絡(luò)傳送給相應(yīng)的用戶，完成更為復(fù)雜的計算、分析以及處理。由于無線傳感器網(wǎng)絡(luò)無需固定設(shè)備支撐，可以快速部署，同時具有易于組網(wǎng)、不受有線網(wǎng)絡(luò)的約束等優(yōu)點，將被廣泛應(yīng)用于災(zāi)難自救、醫(yī)療救護(hù)、環(huán)境檢測、森林火險報警、火山監(jiān)測和軍事領(lǐng)域。

國際上，無線傳感器網(wǎng)絡(luò)引起了學(xué)術(shù)界、軍界和工業(yè)界的極大關(guān)注，許多重要的計算機(jī)和無線通信的研發(fā)組織已深刻地認(rèn)識到了這個問題，進(jìn)行了無線傳感器網(wǎng)絡(luò)的基礎(chǔ)理論和關(guān)鍵技術(shù)的研究。目前由微型傳感器節(jié)點組成的無線傳感器網(wǎng)絡(luò)已經(jīng)發(fā)展成為一個重要的計算平臺。復(fù)雜網(wǎng)絡(luò)是迅速發(fā)展的一門新興學(xué)科，近年來大量復(fù)雜網(wǎng)絡(luò)的研究成果發(fā)表在《Physical?Review?Letters》、《Physical?Review?E》、《Physica?A》和《PANS》等物理類期刊以及《Nature》和《Science》等綜合性期刊上，從一個側(cè)面反映出復(fù)雜網(wǎng)絡(luò)已成為物理界的一個新的研究熱點，其理論基礎(chǔ)是統(tǒng)計物理學(xué)。

無線傳感器網(wǎng)絡(luò)的主要任務(wù)是將網(wǎng)絡(luò)中傳感器節(jié)點收集的數(shù)據(jù)傳送給基站，一種實現(xiàn)該任務(wù)的最簡單方法是直接傳送，即網(wǎng)絡(luò)中的每個節(jié)點把收集的數(shù)據(jù)直接傳送給基站。然而，對于遠(yuǎn)離基站的無線傳感器節(jié)點來說，這將使節(jié)點傳送數(shù)據(jù)消耗的能量代價太高而使節(jié)點很快死亡。為解決這個問題，一些以節(jié)約能量為目的的算法相繼被提出來，目前較主流的是LEACH算法，它首先以自組織的方式隨機(jī)選出部分傳感器節(jié)點作為簇頭，接著選出的簇頭進(jìn)行廣播，普通節(jié)點根據(jù)接受信號的強(qiáng)弱來選擇最近的簇頭加入，并同該簇頭一起形成簇。然后簇中的成員節(jié)點把收集的數(shù)據(jù)傳送給簇頭，簇頭將簇內(nèi)所有成員節(jié)點收集的數(shù)據(jù)與本節(jié)點收集的數(shù)據(jù)進(jìn)行聚合后發(fā)給基站。

另值得一提的是PEGASIS協(xié)議。該協(xié)議把系統(tǒng)中所有無線傳感器節(jié)點用貪婪算法構(gòu)成一個鏈，在每一輪中，任意節(jié)點從位于鏈上的一相鄰接點接收數(shù)據(jù)并把接收到的數(shù)據(jù)與本節(jié)點的數(shù)據(jù)聚合，接著把聚合后的數(shù)據(jù)發(fā)送到鏈上的另一相鄰接點。這種發(fā)送和聚合是從鏈上的端節(jié)點開始，沿著鏈路直到指定節(jié)點，然后由指定節(jié)點把最后聚合的數(shù)據(jù)發(fā)送到基站。與LEACH協(xié)議相比，PEGASIS協(xié)議與基站直接通信的節(jié)點更少而且數(shù)據(jù)聚合能力更強(qiáng)，從而減少了每一輪的能量損耗。但PEGASIS算法是將網(wǎng)絡(luò)中的全部節(jié)點構(gòu)造成一條鏈，如果鏈上的某一節(jié)點死亡則使得從鏈端到該節(jié)點的所有數(shù)據(jù)丟失，因此PEGASIS的容錯性差。PEDAP協(xié)議進(jìn)一步發(fā)展了PEGASIS協(xié)議，其核心思想是把無線傳感器網(wǎng)絡(luò)的所有節(jié)點構(gòu)造成一棵最小匯集樹(Minimum?Spanning?Tree)，每過一定的輪數(shù)后，PEDAP協(xié)議需要基站重新計算路由信息用來排除死亡節(jié)點。然而對于PEDAP這種集中式的算法，如果節(jié)點因非能量耗盡而死亡時，則基站無法排除這類故障而仍然按照原來的信息計算最小匯集樹，從而影響了網(wǎng)絡(luò)拓?fù)涞目煽啃浴Ｔ趯嶋H應(yīng)用中，無線傳感器網(wǎng)絡(luò)往往被部署在人們難以維護(hù)的地區(qū)，在惡劣環(huán)境因素的影響下，傳感器節(jié)點一般具有較高的故障率，當(dāng)網(wǎng)絡(luò)中的一個或多個節(jié)點失效時，收集的數(shù)據(jù)將會丟失。因此人們希望無線傳感器網(wǎng)絡(luò)拓?fù)渚哂辛己玫聂敯粜裕诓糠止?jié)點會受到能量和惡劣環(huán)境影響而失效時，局部失效不應(yīng)該導(dǎo)致失去全局網(wǎng)絡(luò)傳輸信息的能力。

目前針對無線傳感器網(wǎng)絡(luò)結(jié)構(gòu)容錯性的研究涉及較少。已有的文獻(xiàn)與專利都是集中在構(gòu)造k重覆蓋網(wǎng)絡(luò)或增加工作節(jié)點來進(jìn)行的，這些冗余機(jī)制盡管滿足了容錯性的要求，但由于增加了參與通信的節(jié)點個數(shù)，因而降低了系統(tǒng)的性能、影響了網(wǎng)絡(luò)的壽命。復(fù)雜網(wǎng)絡(luò)理論的研究結(jié)果表明，復(fù)雜系統(tǒng)的容錯能力不僅僅存在于這些具有冗余組件的系統(tǒng)，而且也同樣存在于具有無標(biāo)度特征的網(wǎng)絡(luò)之中。

發(fā)明內(nèi)容

本發(fā)明的目的是提供一種無線傳感網(wǎng)中基于隨機(jī)行走的容錯方法，以解決現(xiàn)有技術(shù)的容錯能力差的缺陷。

本發(fā)明提供的無線傳感網(wǎng)中基于隨機(jī)行走的容錯方法包括以下步驟：

1)以基站和它的鄰居簇頭節(jié)點組成的m₀個節(jié)點分別作為初始點，并使基站與它們兩兩相連；

2)隨機(jī)選擇一個簇頭節(jié)點j作為隨機(jī)行走的起始點；