無線傳感器網絡拓撲控制算法范文

本站小編為你精心準備了無線傳感器網絡拓撲控制算法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

1概述

無線傳感器網絡(WirelessSensorNetwork，WSN)近年來的快速發展離不開傳感器技術、網絡無線通信技術、嵌入式技術、分布式信息技術以及微電子制造技術等相關關鍵技術的日益成熟。它是一種無中心節點的全分布系統，是有針對性對某個監控區域內進行隨機投放的若干個傳感器節點自組織通過無線電信通信構成網絡系統。傳感器節點可根據其內置的不同功能的傳感器，感知所在的周遭環境中人們的感興趣的數據，如溫度、紅外線、濕度、壓力、土壤成分、移動物體的屬性等。正因為無線傳感器網絡的無處不在的感知技術優勢，它有著非常廣泛的應用前景。在軍事領域、環境應用、醫療事業、工業應用以及商用等多個領域都占有意義非凡的一席之地。顯然，無線傳感器網絡是當前多學科高度交叉、前沿的熱點研究之一。無線傳感器網絡中傳感器節點一般由數據采集模塊、數據處理和控制模塊、無線通信模塊和供電模塊組成。而正因為它自身的物理特性因素，其電量供給有限成為無線傳感器網絡生命期主要的瓶頸問題之一。早期的經典拓撲控制算法思想主要是借助控制節點傳輸功率或稀疏化網絡拓撲圖，達到降低節點信道之間干擾的目的。近階段有一些研究者，指出機械性減少邊的數量、長度及鄰節點度不一定就能保證節點之間的干擾現象也降低，并就干擾模型的定義和度量方法進行了研究。其中，定義的干擾模型有基于發送節點的干擾模型、基于接收節點的干擾模型。基于不同的干擾模型，文獻［8］指出二維及二維以上的網絡模型的拓撲控制干擾優化問題已被證明屬于NP問題。在上述拓撲控制算法的研究中，很少有以降低全局網絡節點中的最大干擾值作為首要目標，干擾的存在不僅會影響通信質量，而且造成數據不斷重傳損耗電量縮短網絡生命周期［9］，大部分算法針對的都是節點分布比較均勻的網絡情況，而對于節點間非均勻分布的網絡情況，如指數鏈模型無線傳感器網絡下的干擾優化效果甚微。本文將采用基于接收節點干擾模型，以干擾閾值作為重要考慮因素，以最小化最大干擾值、網絡連通性為算法首要目標，對一維指數鏈模型的無線傳感器網絡節點的鄰居節點、節點傳輸半徑和網絡節點數、節點所受的干擾進行研究，設計一種啟發式算法，并將其算法思想沿用至二維網絡模型中，保證其網絡連通性的同時達到優化最大干擾值的目的。

2相關工作

功率控制是研究無線傳感器網絡拓撲控制重要方向之一，功率控制指的是合理地設置或動態調整節點的傳輸半徑功率，在保證整個網絡的連通的同時，弱化節點間的相互干擾，并達到高效節能、延長網絡生命期的目的。文獻［7］指出包含最近鄰居的節點算法(下文簡稱為最近鄰算法)在指數鏈模型上的干擾優化效果不甚理想。在一維指數鏈上若有n個節點以2的指數倍的距離相隔進行排布，由于最近鄰算法的算法特性，會將構成網絡中的最短路徑的鏈路保留下來，以減少鏈路開銷。而一維指數鏈的特性會使得新加入每一條的連接增大原先最右邊的節點的發射半徑，這也加劇了網絡中節點的最大干擾值擴大。如圖1所示，由文獻［7］指出最近鄰算法產生的拓撲結構節點中受到的最大的干擾達到n－2∈n。顯然，一個節點在有n個節點的網絡中，在最壞的情況下，受到除已的其他節點干擾，即干擾值為n－1，可見，最近鄰算法在一維指數鏈上干擾優化的改進效果不如人意。

3干擾模型要素

根據無線傳感器網絡的特性，本文延續文獻［7-8］模型化方法利用單位圓盤圖(UnitDiskGraph，UDG)理論］進行無線傳感器網絡抽象建模。便于討論后文提出的干擾優化拓撲控制算法，本文采用無向圖中的頂點來模擬在監測區域投放的傳感器節點，圖中任意2點存在的邊作為任意2個傳感器節點直接通信即一跳距離的依據。

3．1單位圓盤圖在UDG圖G=(V，E)中，V為圖G中頂點的集合，E為圖G的任意頂點存在邊的集合。V中的每個頂點都有以該頂點為中心的等半徑的圓一一對應，假設所有節點具有相同的通信半徑上限rmax，當且僅當u頂點和v頂點之間的歐氏距離小于等于rmax時，則e(u，v)∈E。根據上述UDG圖的定義，假定UDG圖G=(u，v)為無線傳感器網絡的抽象模型，并設定無線傳感器網絡中的傳感器節點的傳輸功率是可調節的，其有效值區間是［0，MaxPower］，其中，MaxPower代表了節點傳輸功率的上限值。

3．2模型字符為更簡潔明了描述本文要點，將使用以下模型字符進行定義:(1)Nu表示結果拓撲圖T中u節點的鄰居節點集合，即在結果拓撲圖T中與u只有一跳距離的頂點的集合。(2)ru表示結果拓撲圖T中u節點的通信半徑，ru=maxv∈Nu{|u，v|}，其中，|u，v|指的是u節點與v節點之間的歐氏距離。(3)D(u，ru)表示以u為圓盤中心ru為通信半徑所覆蓋的節點的集合，為方便算法展開分析，這里不考慮節點自身覆蓋的情況。(4)本文采用基于接收者的干擾模型，RI(u)表示u節點對于根據拓撲控制得到最終的拓撲圖T=(V，E’)，節點受到干擾是這樣定義。(5)衡量結果拓撲圖的干擾值是由眾節點所受的干擾度最大的那個節點的干擾值所決定。根據3．1節中指出通信功率的上限MaxPower，則同樣的，傳感器節點都受限于同一個最大通信半徑值MaxRadiu，而節點的通信半徑取值隨著拓撲控制調節控制在［0，MaxRadiu］區間，也就是說，無線傳感器網絡中的傳感器節點初始條件都是統一的，當中的最早消耗完電量的節點則是受到干擾最多的那個節點，這也決定了當前無線傳感器網絡的生命期的長度。

4本文算法設計思想

根據上述采用的基于接收者的網絡拓撲干擾模型，本文提出了一種基于干擾閾值調節的拓撲控制(ThresholdAdaptiveTopologyControl，TATC)算法。TATC算法思想主要如下:(1)建立模型:每個節點需要與其他節點進行消息交互，收集搭建鏈路的距離即通信半徑的數據。考慮在理想狀態下，如果網絡中任意u，v節點能通過一跳距離能收到消息響應成功，則根據式(1)，它們之間的通信鏈路距離是不超過設定的單位通信半徑上限單位1，則圖G中u，v點中存在直接鏈路，即e(u，v)∈E。(2)初始化結構拓撲圖T，T=(V，ETATC)，ETATC=NULL。由于當前T中邊為空集，當前RI(T)=0;設定一個干擾閾值RI-threshold初始值為1。(3)隨機遍歷E集合中的鏈路，對鏈路進行預處理選擇，嘗試每一條鏈路逐步加入ETATC集合中，并計算出當前圖T中各個節點RI值，從而得到RI(T)值。(4)對當前假設的圖T中ETATC集合中利用深度搜索算法進行是否存在邊回路檢測，如若存在回路，則ETATC集合中將不會包含該鏈路，與此同時，E集合中也將剔除該鏈路，之后返回步驟(3)，將繼續遍歷下一條鏈路。否則，執行步驟(5)。(5)如果加入鏈路能使RI(T)不超過當前的RI-threshold，則該鏈路將加入ETATC集合中，與此同時，E集合中也將剔除該鏈路。(6)遍歷完畢，延續深度搜索算法檢測圖T連通性，如果不連通，則將當前最大干擾閾值進行向上調整，執行步驟(3)，否則執行步驟(7)。(7)算法執行完畢，得到結果拓撲控制圖T=(V，ETATC)，此時的最大干擾閾值RI-threshold則為當前結果拓撲控制圖T中的RI(T)值。

5拓撲結構性質分析

TATC是一個貪心算法。在進行拓撲控制時，在結果拓撲圖T中的鏈路還未達到所需時，此時，算法中設定的RI-threshold閾值參數相當于當前的目標函數。把所有符合當前的全局最大干擾閾值條件下的鏈路都會包含在ETATC集合中，前提是該鏈路的加入不造成T中有環，如果造成環，直接在初始G中丟棄該鏈路，如果符合當前添加情況，也需在G中剔除該鏈路。繼續檢測拓撲圖T是否為連通圖為該算法的出口的關鍵，如果不為連通圖，需增大RI-threshold閾值參數，繼續上述的步驟(3)。顯而易見，G圖中有m條鏈路，n個節點，每次遍歷的是當前G中鏈路集合。RI-threshold閾值參數在算法中逐步增加，直到圖T構成了一個連通圖。因此，步驟(3)中需要至多遍歷RI-threshold×m次。其中，RI-threshold的取值范圍的上限是n－1，步驟(4)、步驟(5)中會剔除一些冗余的鏈路，步驟(3)再次遍歷時其鏈路集合工作負荷逐漸減輕。同理，步驟(6)對圖T的連通性需檢測RI-threshold次。其中，算法從e(u，v)=E(u，v)∈V，ETATC={•}開始，重復執行以下的操作:在所有e(u，v)=E找到符合一條符合當前RI-threshold閾值參數的邊加入集合ETATC，同時在原集合E中刪除該邊，直至ETATC中有n－1條邊，即圖T為極小連通圖。算法的時間復雜度為O(n2)。如圖3所示，16個節點的一維指數鏈，使用TATC算法所得的結構拓撲圖中產生的最大干擾RI(T)=5，而根據本文第2節中指出的最近鄰算法則在該鏈路上產生的RI(T)=14。

6性能仿真與分析

為評估TATC算法的有效性，根據文獻［8］所介紹的指數鏈特征采用UDG模型分別構建一維指數鏈以及二維指數鏈的初始拓撲結構。如圖4、圖5所示，橫坐標表示當前一維指數鏈網絡中的節點數，縱坐標分別表示當前網絡中節點的最大的干擾值、網絡節點的平均干擾值。圖中比較了最近鄰算法以及本文算法在一維指數鏈產生的拓撲圖中節點中的最大干擾值以及平均干擾值。與最近鄰算法相比，TATC算法顯著減小了網絡中節點的最大干擾值、平均干擾值，而且隨著節點數的增加，拓撲控制后的拓撲圖的最大干擾、平均干擾增長幅度較慢。圖6、圖7仿真的是在區域1000m×1000m的區域中，據二維指數鏈特性［7］排布50個～400個節點，上述的2種算法在該網絡環境產生的拓撲結構圖中的節點的最大干擾值以及平均干擾值。可以明顯看到，采用TATC算法的網絡中的最大干擾值、平均干擾值的數值優于最近鄰算法。

7結束語

本文設計一種基于最大干擾值閾值調節的拓撲控制算法。該算法以網絡連通性、拓撲結構干擾弱化性為目標函數，對干擾閾值不斷自適應調節，直到構造成所需的網絡拓撲結構。實驗結果表明，在指數鏈模型上，該算法能控制節點的最大干擾值在構建拓撲結構中趨于緩慢增長，比最近鄰算法取得了更好的干擾優化效果。但該算法還需進一步改善并推廣至其他網絡模型。今后將從網絡容錯性能和適用性方面上繼續改進該算法，以提升網絡的抗毀性，降低算法的局限性。

作者：謝曉虹 曾碧卿 單位：華南師范大學計算機學院 華南師范大學軟件學院