一種高可靠低能耗的無線傳感器網絡拓撲方法

辛強偉 唐云凱 許曉婷

摘要：過多的跳數對于無線傳感器網絡的效率和可靠性都不利。本文提出環形最小連通支配集方法，從拓撲的角度來探討該方法對無線傳感器網絡可靠性和能耗的影響。最小連通支配集可有效地減小網絡的跳數，環形拓撲可提高可靠性，因而環形最小連通支配集方法可實現網絡的高可靠性和低能耗。

關鍵詞：無線傳感器網絡；最小連通支配集；拓撲

中圖分類號：TP393 文獻標識碼：A 文章編號：1007-9416（2018）08-0055-02

1 引言

實際應用存在大規模無線傳感器網絡，例如森林監測、城市智能交通管理系統和大型社區監測等，這些實際應用需要部署大量的傳感器節點。無線傳感器網絡中節點通過自組織形成一定的拓撲，通過形成的連接通信。由于節點通信距離的限制，無線傳感器網絡采用多跳的方式傳輸數據。無線傳輸的不穩定導致轉發可能會出現丟包，轉發次數越多丟包越嚴重。一次轉發時間很短，但多次轉發累積消耗的時間對于實時控制系統不容忽視。此外，有的路由機制采取發送數據包后，若對方在設定的時間內不應答，則重傳數據包，而重傳會降低網絡的效率和增大網絡的時延。

大規模無線傳感器網絡的平均跳數往往較大。過多的跳數可導致能耗增加、丟包率上升、延遲增大以及可靠性變差。減少冗余轉發節點對于大規模無線傳感器網絡具有重要意義。大規模無線傳感器網絡的要求之一是低能耗。此外，高可靠性也是大規模無線傳感器網絡的要求。本文研究如何實現大規模無線傳感器網絡的高可靠性和低能耗。

2 已有工作

目前對于無線傳感器網絡最小連通支配集的研究主要集中在減少能量的消耗，達到延長網絡的生存時間。最小連通支配集方法可避免泛洪，減少冗余轉發節點[1]。增加處于睡眠狀態的節點即非支配點的數目，可以達到降低網絡能耗的目的。

最小連通支配集法容錯的研究比較少，當最小連通支配集中有節點故障或失效時可以修復。基于能量代價的最小權和支配集拓撲控制算法考慮了節點能量[2]。根據各節點之間的能量和距離等因素，用加權的方式來構建和分析最小連通支配集。為了延長網絡生存時間，用馬爾科夫模型優化最小連通支配集算法[3]。

3 環形最小連通支配集分析

相同條件下，隨著跳數的增加，丟包率會呈現上升的趨勢。因此較少無線傳感器網絡的跳數對于實現高效互連很重要。本文通過建立環形最小連通支配集來減小無線傳感器網絡中的跳數并且提高網絡的可靠性。

3.1 平均跳數最小化

無線傳感器網絡的平均跳數為任意兩個節點之間的跳數的平均值。最小連通支配集目的是讓盡量多的節點處于休眠狀態，最大限度地減少中間轉發節點。在拓撲控制中應用最小連通支配集可以減少冗余轉發節點，為實現高效無線傳感器網絡提供了保證。

無線傳感器網絡的節點部署密度加大時，會造成連通率的增大。平均跳數和連通率有著一定的聯系。隨機部署在一區域內的無線傳感器網絡節點的度分布近似于Poisson分布，屬于均勻網絡。無線傳感器網絡節點的度受節點通信距離的限制，因而如果隨機部署節點可能會形成多數節點的度相近。連通率與無線傳感器網絡的平均度成正比，當網絡的平均度達到一定程度后，即當節點部署達到一定程度后，再繼續增加節點數目，連通率會保持不變。

無線傳感器網絡的傳輸效率取決于節點數目和平均跳數。當節點密度偏低時，會有一些節點不能連通，這時最小連通支配集表現為較少的構成節點。隨著節點密度的增大，無線傳感器網絡的連通性逐步增強。隨著節點數目的增大，最小連通支配集變大。當節點密度達到一定水平時，最小連通支配集的大小趨于穩定。

最大跳數的意義在于可被視為最壞情況，平均跳數的意義在于可被視為一般情況。設計和分析無線傳感器網絡時如果對系統有很高容錯要求，應準備最壞情況的發生，即準備最大跳數的出現。隨著節點數目的增加，最大跳數變大。當節點密度達到一定水平時，最大跳數趨于穩定。

隨機部署節點隨著節點密度的增大，平均跳數逐漸出現小幅下降的趨勢。當節點還相對稀疏時，會有一些節點相互之間不能連通。在全面連通之后繼續增加節點，會產生冗余節點，使得網絡具備一定的容錯性。因此一定的冗余是必要的。

當節點密度較低時，隨著節點數目的增大，平均跳數較快增大。當節點密度達到一定水平后，平均跳數逐漸小幅減小。隨著節點數目的增加會出現兩個階段：第一個階段是當連通率尚未達到1時，隨著節點數目的增加，平均跳數處于上升的趨勢；第二個階段是當連通率達到1后，隨著節點數目的增加，平均跳數處于下降的趨勢。隨機部署時全面連通所需的節點數目可以用來衡量算法的優劣。在達到全面連通后繼續增加節點會減小跳數，從而提高網絡效率和加強網絡容錯。

3.2 可調節的環形結構

最小連通支配集是一個圖論里的概念，支配集中包含的是骨干節點，骨干節點之間可以通信，而且骨干節點的數目最小。環形最小連通支配集的特點是閉環結構，可運用自愈環對網絡進行自動保護，從而可以顯著提高無線傳感器網絡的可靠性。

環型網絡拓撲結構是一種連接成封閉回路的結構。環形最小連通支配集從網絡結構上看，各骨干節點間是直接串聯、首尾相接、有輸入和輸出、輸出能返回到輸入并產生影響。這樣任何一個骨干節點出現故障都會造成最小連通支配集的中斷，因而會在第一時間發現。另一方面，該方法也是一種具有反饋的機制，可以根據返回的參數進行網絡的調節。

傳感器節點由于采用電池供電容易因電量耗盡而失效，此外故障和人為破壞也會造成傳感器節點失效。最小連通支配集是骨干節點并非普通節點，其失效會對網絡造成重要影響，需要采用環形結構第一時間發現并進行解決，從而提高網絡的可靠性。

4 結語

高可靠性和低能耗是無線傳感器網絡的重要要求，由于多跳會帶來時延影響網絡效率以及增大能耗，因而減少無線傳感器網絡的跳數具有現實意義。本文探討了最小連通支配集對跳數的影響以及網絡跳數和連通率之間的關系。使用環形最小連通支配集法可以有效地減小最大跳數和平均跳數并且較好地提高網絡可靠性，從而達到建立高可靠低能耗的無線傳感器網絡。

參考文獻

[1]唐勇，周明天.基于極大獨立集的最小連通支配集的分布式算法[J].電子學報，2007，32（4）：868-874.

[2]孫超，尹榮榮，郝曉辰，劉彬.WSNs中基于能量代價的最小權和支配集拓撲控制算法[J].電子與信息學報，2010，32（4）：857-863.

[3]汪文勇，向渝，董傳坤，楊挺，唐勇.用馬爾科夫模型優化分布式最小連通支配集算法[J].電子學報，2010，38（10）：2441-2446.