一種干擾優(yōu)化無線傳感器網(wǎng)絡(luò)拓撲控制算法

謝曉虹，曾碧卿

（1.華南師范大學計算機學院，廣州510631；2.華南師范大學軟件學院，廣東佛山528225）

一種干擾優(yōu)化無線傳感器網(wǎng)絡(luò)拓撲控制算法

謝曉虹1，曾碧卿2

（1.華南師范大學計算機學院，廣州510631；2.華南師范大學軟件學院，廣東佛山528225）

針對如何準確度量無線傳感器網(wǎng)絡(luò)中的干擾，并構(gòu)建最小化最大干擾值拓撲結(jié)構(gòu)的問題，根據(jù)傳感器節(jié)點的特點以及無線通信機制，提出一種閾值調(diào)節(jié)的拓撲控制算法。網(wǎng)絡(luò)中每個節(jié)點收集鄰居節(jié)點相關(guān)信息，同時以干擾閾值為目標函數(shù)，選取符合當前干擾閾值以及不會使當前拓撲圖產(chǎn)生回路的鏈路進行拓撲構(gòu)建，直至拓撲連通，實現(xiàn)整個網(wǎng)絡(luò)中節(jié)點最大干擾最小化。仿真結(jié)果表明，在無線傳感器網(wǎng)絡(luò)指數(shù)鏈模型下，與最近鄰算法相比，該算法生成的拓撲控制結(jié)構(gòu)干擾優(yōu)化效果更優(yōu)，并能保證網(wǎng)絡(luò)的連通性及更有效地延長網(wǎng)絡(luò)的生存周期。

無線傳感器網(wǎng)絡(luò)；閾值控制；指數(shù)鏈模型；干擾優(yōu)化；拓撲控制

1 概述

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）近年來的快速發(fā)展離不開傳感器技術(shù)、網(wǎng)絡(luò)無線通信技術(shù)、嵌入式技術(shù)、分布式信息技術(shù)以及微電子制造技術(shù)等相關(guān)關(guān)鍵技術(shù)的日益成熟。它是一種無中心節(jié)點的全分布系統(tǒng)，是有針對性對某個監(jiān)控區(qū)域內(nèi)進行隨機投放的若干個傳感器節(jié)點自組織通過無線電信通信構(gòu)成網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點可根據(jù)其內(nèi)置的不同功能的傳感器，感知所在的周遭環(huán)境中人們的感興趣的數(shù)據(jù)，如溫度、紅外線、濕度、壓力、土壤成分、移動物體的屬性等［1］。正因為無線傳感器網(wǎng)絡(luò)的無處不在的感知技術(shù)優(yōu)勢，它有著非常廣泛的應(yīng)用前景。在軍事領(lǐng)域、環(huán)境應(yīng)用、醫(yī)療事業(yè)、工業(yè)應(yīng)用以及商用等多個領(lǐng)域都占有意義非凡的一席之地。顯然，無線傳感器網(wǎng)絡(luò)是當前多學科高度交叉、前沿的熱點研究之一。無線傳感器網(wǎng)絡(luò)中傳感器節(jié)點一般由數(shù)據(jù)采集模塊、數(shù)據(jù)處理和控制模塊、無線通信模塊和供電模塊組成［2］。而正因為它自身的物理特性因素，其電量供給［3］有限成為無線傳感器網(wǎng)絡(luò)生命期主要的瓶頸問題之一。

早期的經(jīng)典拓撲控制算法思想主要是借助控制節(jié)點傳輸功率或稀疏化網(wǎng)絡(luò)拓撲圖［4］，達到降低節(jié)點信道之間干擾的目的。近階段有一些研究者，指出機械性減少邊的數(shù)量、長度及鄰節(jié)點度不一定就能保證節(jié)點之間的干擾現(xiàn)象也降低［5-7］，并就干擾模型的定義和度量方法進行了研究。其中，定義的干擾模型有基于發(fā)送節(jié)點的干擾模型、基于接收節(jié)點的干擾模型。基于不同的干擾模型，文獻［8］指出二維及二維以上的網(wǎng)絡(luò)模型的拓撲控制干擾優(yōu)化問題已被證明屬于NP問題。

在上述拓撲控制算法的研究中，很少有以降低全局網(wǎng)絡(luò)節(jié)點中的最大干擾值作為首要目標，干擾的存在不僅會影響通信質(zhì)量，而且造成數(shù)據(jù)不斷重傳損耗電量縮短網(wǎng)絡(luò)生命周期［9］，大部分算法針對的都是節(jié)點分布比較均勻的網(wǎng)絡(luò)情況，而對于節(jié)點間非均勻分布的網(wǎng)絡(luò)情況，如指數(shù)鏈模型無線傳感器網(wǎng)絡(luò)下的干擾優(yōu)化效果甚微。本文將采用基于接收節(jié)點干擾模型，以干擾閾值作為重要考慮因素，以最小化最大干擾值、網(wǎng)絡(luò)連通性為算法首要目標，對一維指數(shù)鏈模型的無線傳感器網(wǎng)絡(luò)節(jié)點的鄰居節(jié)點、節(jié)點傳輸半徑和網(wǎng)絡(luò)節(jié)點數(shù)、節(jié)點所受的干擾進行研究，設(shè)計一種啟發(fā)式算法，并將其算法思想沿用至二維網(wǎng)絡(luò)模型中，保證其網(wǎng)絡(luò)連通性的同時達到優(yōu)化最大干擾值的目的。

2 相關(guān)工作

功率控制［10］是研究無線傳感器網(wǎng)絡(luò)拓撲控制重要方向之一，功率控制指的是合理地設(shè)置或動態(tài)調(diào)整節(jié)點的傳輸半徑功率，在保證整個網(wǎng)絡(luò)的連通的同時，弱化節(jié)點間的相互干擾［11-13］，并達到高效節(jié)能、延長網(wǎng)絡(luò)生命期的目的。文獻［7］指出包含最近鄰居的節(jié)點算法（下文簡稱為最近鄰算法）在指數(shù)鏈模型上的干擾優(yōu)化效果不甚理想。在一維指數(shù)鏈上若有n個節(jié)點以2的指數(shù)倍的距離相隔進行排布，由于最近鄰算法的算法特性，會將構(gòu)成網(wǎng)絡(luò)中的最短路徑的鏈路保留下來，以減少鏈路開銷。而一維指數(shù)鏈的特性會使得新加入每一條的連接增大原先最右邊的節(jié)點的發(fā)射半徑，這也加劇了網(wǎng)絡(luò)中節(jié)點的最大干擾值擴大。

如圖1所示，由文獻［7］指出最近鄰算法產(chǎn)生的拓撲結(jié)構(gòu)節(jié)點中受到的最大的干擾達到n-2∈n。顯然，一個節(jié)點在有n個節(jié)點的網(wǎng)絡(luò)中，在最壞的情況下，受到除已的其他節(jié)點干擾，即干擾值為n-1，可見，最近鄰算法在一維指數(shù)鏈上干擾優(yōu)化的改進效果不如人意。

圖1 最近鄰算法構(gòu)建拓撲控制的過程

3 干擾模型要素

根據(jù)無線傳感器網(wǎng)絡(luò)的特性，本文延續(xù)文獻［7-8］模型化方法利用單位圓盤圖（Unit Disk Graph，UDG）理論［13］進行無線傳感器網(wǎng)絡(luò)抽象建模。便于討論后文提出的干擾優(yōu)化拓撲控制算法，本文采用無向圖中的頂點來模擬在監(jiān)測區(qū)域投放的傳感器節(jié)點，圖中任意2點存在的邊作為任意2個傳感器節(jié)點直接通信即一跳距離的依據(jù)。

3.1 單位圓盤圖

在UDG圖G=（V，E）中，V為圖G中頂點的集合，E為圖G的任意頂點存在邊的集合。V中的每個頂點都有以該頂點為中心的等半徑的圓一一對應(yīng)，假設(shè)所有節(jié)點具有相同的通信半徑上限r(nóng)max，當且僅當u頂點和v頂點之間的歐氏距離小于等于rmax時，則e（u，v）∈E。UDG圖頂點的通信半徑r，一般指定為單位1，關(guān)系數(shù)學表達式如下：

根據(jù)上述UDG圖的定義，假定UDG圖G=（u，v）為無線傳感器網(wǎng)絡(luò)的抽象模型，并設(shè)定無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點的傳輸功率是可調(diào)節(jié)的，其有效值區(qū)間是［0，MaxPower］，其中，MaxPower代表了節(jié)點傳輸功率的上限值。

3.2 模型字符

為更簡潔明了描述本文要點，將使用以下模型字符進行定義：

（1）Nu表示結(jié)果拓撲圖T中u節(jié)點的鄰居節(jié)點集合，即在結(jié)果拓撲圖T中與u只有一跳距離的頂點的集合。

（2）ru表示結(jié)果拓撲圖T中u節(jié)點的通信半徑，ru=maxv∈Nu｛|u，v|｝，其中，|u，v|指的是u節(jié)點與v節(jié)點之間的歐氏距離。

（3）D（u，ru）表示以u為圓盤中心ru為通信半徑所覆蓋的節(jié)點的集合，為方便算法展開分析，這里不考慮節(jié)點自身覆蓋的情況。

（4）本文采用基于接收者的干擾模型，RI（u）表示u節(jié)點對于根據(jù)拓撲控制得到最終的拓撲圖T=（V，E'），節(jié)點受到干擾是這樣定義的：

如圖2所示，每個節(jié)點所選用的傳輸半徑受其最遠的鄰居節(jié)點影響，則u節(jié)點選用k1作為它的通信半徑，v節(jié)點選用k2作為通信半徑。根據(jù)式（2），可計算u，v節(jié)點所受到的干擾值分別為RI（u）=2，RI（v）=3。

圖2 基于接收者的干擾模型

（5）衡量結(jié)果拓撲圖的干擾值是由眾節(jié)點所受的干擾度最大的那個節(jié)點的干擾值所決定。根據(jù)3.1節(jié)中指出通信功率的上限MaxPower，則同樣的，傳感器節(jié)點都受限于同一個最大通信半徑值MaxRadiu，而節(jié)點的通信半徑取值隨著拓撲控制調(diào)節(jié)控制在［0，MaxRadiu］區(qū)間，也就是說，無線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點初始條件都是統(tǒng)一的，當中的最早消耗完電量的節(jié)點則是受到干擾最多的那個節(jié)點，這也決定了當前無線傳感器網(wǎng)絡(luò)的生命期的長度。因此，本文取圖T節(jié)點中RI（v）值最大者作為該算法產(chǎn)生的拓撲圖干擾：

（6）圖2中受到的平均干擾可定義為：

4 本文算法設(shè)計思想

根據(jù)上述采用的基于接收者的網(wǎng)絡(luò)拓撲干擾模型，本文提出了一種基于干擾閾值調(diào)節(jié)的拓撲控制（Threshold Adaptive Topology Control，TATC）算法。TATC算法思想主要如下：

（1）建立模型：每個節(jié)點需要與其他節(jié)點進行消息交互，收集搭建鏈路的距離即通信半徑的數(shù)據(jù)。考慮在理想狀態(tài)下，如果網(wǎng)絡(luò)中任意u，v節(jié)點能通過一跳距離能收到消息響應(yīng)成功，則根據(jù)式（1），它們之間的通信鏈路距離是不超過設(shè)定的單位通信半徑上限單位1，則圖G中u，v點中存在直接鏈路，即e（u，v）∈E。消息信息收集處理完畢，可搭建成初始拓撲圖G：

（2）初始化結(jié)構(gòu)拓撲圖T，T=（V，ETATC），ETATC= NULL。由于當前T中邊為空集，當前RI（T）=0；設(shè)定一個干擾閾值RI-threshold初始值為1。

（3）隨機遍歷E集合中的鏈路，對鏈路進行預(yù)處理選擇，嘗試每一條鏈路逐步加入ETATC集合中，并計算出當前圖T中各個節(jié)點RI值，從而得到RI（T）值。

（4）對當前假設(shè)的圖T中ETATC集合中利用深度搜索算法進行是否存在邊回路檢測，如若存在回路，則ETATC集合中將不會包含該鏈路，與此同時，E集合中也將剔除該鏈路，之后返回步驟（3），將繼續(xù)遍歷下一條鏈路。否則，執(zhí)行步驟（5）。

（5）如果加入鏈路能使RI（T）不超過當前的RI-threshold，則該鏈路將加入ETATC集合中，與此同時，E集合中也將剔除該鏈路。

（6）遍歷完畢，延續(xù)深度搜索算法檢測圖T連通性，如果不連通，則將當前最大干擾閾值進行向上調(diào)整，執(zhí)行步驟（3），否則執(zhí)行步驟（7）。

（7）算法執(zhí)行完畢，得到結(jié)果拓撲控制圖T=（V，ETATC），此時的最大干擾閾值RI-threshold則為當前結(jié)果拓撲控制圖T中的RI（T）值。

5 拓撲結(jié)構(gòu)性質(zhì)分析

TATC是一個貪心算法。在進行拓撲控制時，在結(jié)果拓撲圖T中的鏈路還未達到所需時，此時，算法中設(shè)定的RI-threshold閾值參數(shù)相當于當前的目標函數(shù)。把所有符合當前的全局最大干擾閾值條件下的鏈路都會包含在ETATC集合中，前提是該鏈路的加入不造成T中有環(huán)，如果造成環(huán)，直接在初始G中丟棄該鏈路，如果符合當前添加情況，也需在G中剔除該鏈路。繼續(xù)檢測拓撲圖T是否為連通圖為該算法的出口的關(guān)鍵，如果不為連通圖，需增大RI-threshold閾值參數(shù)，繼續(xù)上述的步驟（3）。顯而易見，G圖中有m條鏈路，n個節(jié)點，每次遍歷的是當前G中鏈路集合。RI-threshold閾值參數(shù)在算法中逐步增加，直到圖T構(gòu)成了一個連通圖。因此，步驟（3）中需要至多遍歷RI-threshold×m次。其中，RI-threshold的取值范圍的上限是n-1，步驟（4）、步驟（5）中會剔除一些冗余的鏈路，步驟（3）再次遍歷時其鏈路集合工作負荷逐漸減輕。同理，步驟（6）對圖T的連通性需檢測RI-threshold次。其中，算法從e（u，v）=E（u，v）∈V，ETATC=｛·｝開始，重復(fù)執(zhí)行以下的操作：在所有e（u，v）=E找到符合一條符合當前RI-。

證明：如圖3所示，一維指數(shù)鏈上有n個節(jié)點按照2i倍數(shù)增長分布。可觀察到RI-threshold閾值參數(shù)變化，就會有新的節(jié)點與最左邊的節(jié)點相連，RI-threshold為1時，從左至右，v0連接v1，為2時，v2連接v3并連接v0，為3時，v4連接v0，并連接v5，v6，以此類推，當此時的RI-threshold為RI（n）（RI（n）＞2）時，其至少能連（（RI（n）-1）+（RI（n）-2）+…+1+2）個節(jié)點：threshold閾值參數(shù)的邊加入集合ETATC，同時在原集合E中刪除該邊，直至ETATC中有n-1條邊，即圖T為極小連通圖。算法的時間復(fù)雜度為O（n2）。

定理 在一維指數(shù)鏈圖G，應(yīng)用TATC算法構(gòu)造拓撲圖的

圖3 一維指數(shù)鏈上本文算法產(chǎn)生的結(jié)果拓撲結(jié)構(gòu)

如圖3所示，16個節(jié)點的一維指數(shù)鏈，使用TATC算法所得的結(jié)構(gòu)拓撲圖中產(chǎn)生的最大干擾RI（T）=5，而根據(jù)本文第2節(jié)中指出的最近鄰算法則在該鏈路上產(chǎn)生的RI（T）=14。

6 性能仿真與分析

為評估TATC算法的有效性，根據(jù)文獻［8］所介紹的指數(shù)鏈特征采用UDG模型分別構(gòu)建一維指數(shù)鏈以及二維指數(shù)鏈的初始拓撲結(jié)構(gòu)。

如圖4、圖5所示，橫坐標表示當前一維指數(shù)鏈網(wǎng)絡(luò)中的節(jié)點數(shù)，縱坐標分別表示當前網(wǎng)絡(luò)中節(jié)點的最大的干擾值、網(wǎng)絡(luò)節(jié)點的平均干擾值。圖中比較了最近鄰算法以及本文算法在一維指數(shù)鏈產(chǎn)生的拓撲圖中節(jié)點中的最大干擾值以及平均干擾值。與最近鄰算法相比，TATC算法顯著減小了網(wǎng)絡(luò)中節(jié)點的最大干擾值、平均干擾值，而且隨著節(jié)點數(shù)的增加，拓撲控制后的拓撲圖的最大干擾、平均干擾增長幅度較慢。

圖4 一維指數(shù)鏈網(wǎng)絡(luò)中的最大干擾值比較

圖5 一維指數(shù)鏈網(wǎng)絡(luò)中的平均干擾值比較

圖6 、圖7仿真的是在區(qū)域1 000 m×1 000 m的區(qū)域中，據(jù)二維指數(shù)鏈特性［7］排布50個～400個節(jié)點，上述的2種算法在該網(wǎng)絡(luò)環(huán)境產(chǎn)生的拓撲結(jié)構(gòu)圖中的節(jié)點的最大干擾值以及平均干擾值。可以明顯看到，采用TATC算法的網(wǎng)絡(luò)中的最大干擾值、平均干擾值的數(shù)值優(yōu)于最近鄰算法。

圖6 二維指數(shù)鏈網(wǎng)絡(luò)中的最大干擾值比較

圖7 二維指數(shù)鏈網(wǎng)絡(luò)中的平均干擾值比較

7 結(jié)束語

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

［1］ 吳成洪.無線傳感器網(wǎng)絡(luò)拓撲控制研究［D］.西安：西安電子科技大學，2010.

［2］ 江 勇，趙 倩.一種應(yīng)用強化學習的自適應(yīng)無線傳感器網(wǎng)絡(luò)路由算法［J］.小型微型計算機系統(tǒng)，2013，34（8）：1723-1727.

［3］ Deshpande A，Montiel C，McLauchlan L.W ireless Sensor Networks——A Comparative Study for Energy Minimization Using Topology Control［C］//Proceedings of the 6th Annual IEEE Green Technologies Conference. Washington D.C.，USA：IEEE Press，2014：44-48.

［4］ 任月清，徐立新.無線傳感器網(wǎng)絡(luò)拓撲連通性與稀疏性研究［J］.傳感技術(shù)學報，2011，24（7）：1038-1042.

［5］ Burkhart M，Von R P，Wattenhofer R，et al.Does Topology Control Reduce Interference［C］//Proceedings of the 5th ACM International Symposium on Mobile Ad Hoc Networking and Computing.New York，USA：ACM Press，2004：9-19.

［6］ Santi P.Topology Control in Wireless Ad Hoc and Sensor Networks［J］.ACM Computing Surveys，2005，37（2）：164-194.

［7］ Rickenbach P V，Schmid S，Wattenhofer R，et al.A Robust Interference Model for Wireless Ad-hoc Networks［C］// Proceedings of the 5th International Workshop on Algorithms for Wireless，Mobile，Ad Hoc and Sensor Networks. Washington D.C.，USA：IEEE Press，2005：239-247.

［8］ Tan Haisheng，Lou Tiancheng，Wang Yuexuan，et al. Exact Algorithm s to Minimize Interference in Wireless Sensor Networks［J］.Theoretical Computing Science，2011，412（50）：6913-6925.

［9］ 李曉鴻，王文艷，王 東.一種最大化Ad Hoc網(wǎng)絡(luò)生存期的拓撲控制算法［J］.計算機研究與發(fā)展，2013，50（3）：461-471.

［10］ 孫 超，尹榮榮，郝曉辰，等.異構(gòu)無線傳感器網(wǎng)絡(luò)支配集拓撲控制算法［J］.軟件學報，2011，22（9）：2137-2148.

［11］ Moscibroda T，Wattenhofer R.Minimizing Interference in Ad Hoc and Sensor Networks［C］//Proceedings of Joint Workshop on Foundations of Mobile Computing. New York，USA：ACM Press，2005：24-33.

［12］ 路 綱，周明天，牛新征，等.無線網(wǎng)絡(luò)鄰近圖綜述［J］.軟件學報，2008，19（4）：888-911.

［13］ Rickenbach V P，Wattenhofer R，Zollinger A.Algorithmic Models of Interference in Wireless Ad Hoc and Sensor Networks［J］.IEEE/ACM Transactions on Networking，2009，17（1）：172-185.

編輯 劉 冰

An Interference-optimization Topology Control Algorithm in Wireless Sensor Network

XIE Xiaohong1，ZENG Biqing2
（1.School of Computing，South China Normal University，Guangzhou 510631，China；2.School of Software，South China Normal University，F(xiàn)oshan 528225，China）

Researching the solution to the problem that how to measure the interference accurately and construct the topological structure with minimizing interference in the Wireless Sensor Network（WSN），it proposes topology control algorithm of threshold adjustment.It can minimize the interference heuristically in exponential node chain network model. In the network，each node collects useful information of its neighbor nodes，and at the same time，with the interference threshold as the objective function，it selects the link between the nodes，which are in line with current interference threshold and don't make the current topology generate loop path.It constructs topology until the topology becomes connected graph，which can minimize the maximum interference among the nodes in the network.Simulation results show that，the new algorithm compared with the nearest algorithm on the exponential node chain network model of WSN，the interference generated topology control structure optimization effect is better，and can guarantee the connectivity of the network and more effectively prolong the lifecycle of the network.

Wireless Sensor Network（WSN）；threshold control；index chain model；interference-optimization；topology control

謝曉虹，曾碧卿.一種干擾優(yōu)化無線傳感器網(wǎng)絡(luò)拓撲控制算法［J］.計算機工程，2015，41（11）：131-134，141.

英文引用格式：Xie Xiaohong，Zeng Biqing.An Interference-optimization Topology Control Algorithm in Wireless Sensor Network［J］.Computer Engineering，2015，41（11）：131-134，141.

1000-3428（2015）11-0131-04

A

TP391

10.3969/j.issn.1000-3428.2015.11.023

國家自然科學基金資助項目（71272144）；廣州市科技計劃基金資助項目（2013KP084）。

謝曉虹（1990-），女，碩士研究生，主研方向：無線傳感器網(wǎng)絡(luò)；曾碧卿，教授、博士。

2014-10-29

2014-12-23 E-m ail：zengbiqing0528@163.com