一種干擾優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?/h1>
2015-12-06 06:11:20謝曉虹曾碧卿
計(jì)算機(jī)工程 2015年11期
謝曉虹，曾碧卿
（1.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州510631；2.華南師范大學(xué)軟件學(xué)院，廣東佛山528225）
一種干擾優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?/p>
謝曉虹1，曾碧卿2
（1.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州510631；2.華南師范大學(xué)軟件學(xué)院，廣東佛山528225）
針對(duì)如何準(zhǔn)確度量無(wú)線傳感器網(wǎng)絡(luò)中的干擾，并構(gòu)建最小化最大干擾值拓?fù)浣Y(jié)構(gòu)的問(wèn)題，根據(jù)傳感器節(jié)點(diǎn)的特點(diǎn)以及無(wú)線通信機(jī)制，提出一種閾值調(diào)節(jié)的拓?fù)淇刂扑惴?。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)收集鄰居節(jié)點(diǎn)相關(guān)信息，同時(shí)以干擾閾值為目標(biāo)函數(shù)，選取符合當(dāng)前干擾閾值以及不會(huì)使當(dāng)前拓?fù)鋱D產(chǎn)生回路的鏈路進(jìn)行拓?fù)錁?gòu)建，直至拓?fù)溥B通，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)最大干擾最小化。仿真結(jié)果表明，在無(wú)線傳感器網(wǎng)絡(luò)指數(shù)鏈模型下，與最近鄰算法相比，該算法生成的拓?fù)淇刂平Y(jié)構(gòu)干擾優(yōu)化效果更優(yōu)，并能保證網(wǎng)絡(luò)的連通性及更有效地延長(zhǎng)網(wǎng)絡(luò)的生存周期。
無(wú)線傳感器網(wǎng)絡(luò)；閾值控制；指數(shù)鏈模型；干擾優(yōu)化；拓?fù)淇刂?/p>
1 概述
無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）近年來(lái)的快速發(fā)展離不開(kāi)傳感器技術(shù)、網(wǎng)絡(luò)無(wú)線通信技術(shù)、嵌入式技術(shù)、分布式信息技術(shù)以及微電子制造技術(shù)等相關(guān)關(guān)鍵技術(shù)的日益成熟。它是一種無(wú)中心節(jié)點(diǎn)的全分布系統(tǒng)，是有針對(duì)性對(duì)某個(gè)監(jiān)控區(qū)域內(nèi)進(jìn)行隨機(jī)投放的若干個(gè)傳感器節(jié)點(diǎn)自組織通過(guò)無(wú)線電信通信構(gòu)成網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點(diǎn)可根據(jù)其內(nèi)置的不同功能的傳感器，感知所在的周遭環(huán)境中人們的感興趣的數(shù)據(jù)，如溫度、紅外線、濕度、壓力、土壤成分、移動(dòng)物體的屬性等［1］。正因?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)的無(wú)處不在的感知技術(shù)優(yōu)勢(shì)，它有著非常廣泛的應(yīng)用前景。在軍事領(lǐng)域、環(huán)境應(yīng)用、醫(yī)療事業(yè)、工業(yè)應(yīng)用以及商用等多個(gè)領(lǐng)域都占有意義非凡的一席之地。顯然，無(wú)線傳感器網(wǎng)絡(luò)是當(dāng)前多學(xué)科高度交叉、前沿的熱點(diǎn)研究之一。無(wú)線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)一般由數(shù)據(jù)采集模塊、數(shù)據(jù)處理和控制模塊、無(wú)線通信模塊和供電模塊組成［2］。而正因?yàn)樗陨淼奈锢硖匦砸蛩兀潆娏抗┙o［3］有限成為無(wú)線傳感器網(wǎng)絡(luò)生命期主要的瓶頸問(wèn)題之一。
早期的經(jīng)典拓?fù)淇刂扑惴ㄋ枷胫饕墙柚刂乒?jié)點(diǎn)傳輸功率或稀疏化網(wǎng)絡(luò)拓?fù)鋱D［4］，達(dá)到降低節(jié)點(diǎn)信道之間干擾的目的。近階段有一些研究者，指出機(jī)械性減少邊的數(shù)量、長(zhǎng)度及鄰節(jié)點(diǎn)度不一定就能保證節(jié)點(diǎn)之間的干擾現(xiàn)象也降低［5-7］，并就干擾模型的定義和度量方法進(jìn)行了研究。其中，定義的干擾模型有基于發(fā)送節(jié)點(diǎn)的干擾模型、基于接收節(jié)點(diǎn)的干擾模型?；诓煌母蓴_模型，文獻(xiàn)［8］指出二維及二維以上的網(wǎng)絡(luò)模型的拓?fù)淇刂聘蓴_優(yōu)化問(wèn)題已被證明屬于NP問(wèn)題。
在上述拓?fù)淇刂扑惴ǖ难芯恐?，很少有以降低全局網(wǎng)絡(luò)節(jié)點(diǎn)中的最大干擾值作為首要目標(biāo)，干擾的存在不僅會(huì)影響通信質(zhì)量，而且造成數(shù)據(jù)不斷重傳損耗電量縮短網(wǎng)絡(luò)生命周期［9］，大部分算法針對(duì)的都是節(jié)點(diǎn)分布比較均勻的網(wǎng)絡(luò)情況，而對(duì)于節(jié)點(diǎn)間非均勻分布的網(wǎng)絡(luò)情況，如指數(shù)鏈模型無(wú)線傳感器網(wǎng)絡(luò)下的干擾優(yōu)化效果甚微。本文將采用基于接收節(jié)點(diǎn)干擾模型，以干擾閾值作為重要考慮因素，以最小化最大干擾值、網(wǎng)絡(luò)連通性為算法首要目標(biāo)，對(duì)一維指數(shù)鏈模型的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)、節(jié)點(diǎn)傳輸半徑和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)所受的干擾進(jìn)行研究，設(shè)計(jì)一種啟發(fā)式算法，并將其算法思想沿用至二維網(wǎng)絡(luò)模型中，保證其網(wǎng)絡(luò)連通性的同時(shí)達(dá)到優(yōu)化最大干擾值的目的。
2 相關(guān)工作
功率控制［10］是研究無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂浦匾较蛑唬β士刂浦傅氖呛侠淼卦O(shè)置或動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的傳輸半徑功率，在保證整個(gè)網(wǎng)絡(luò)的連通的同時(shí)，弱化節(jié)點(diǎn)間的相互干擾［11-13］，并達(dá)到高效節(jié)能、延長(zhǎng)網(wǎng)絡(luò)生命期的目的。文獻(xiàn)［7］指出包含最近鄰居的節(jié)點(diǎn)算法（下文簡(jiǎn)稱為最近鄰算法）在指數(shù)鏈模型上的干擾優(yōu)化效果不甚理想。在一維指數(shù)鏈上若有n個(gè)節(jié)點(diǎn)以2的指數(shù)倍的距離相隔進(jìn)行排布，由于最近鄰算法的算法特性，會(huì)將構(gòu)成網(wǎng)絡(luò)中的最短路徑的鏈路保留下來(lái)，以減少鏈路開(kāi)銷。而一維指數(shù)鏈的特性會(huì)使得新加入每一條的連接增大原先最右邊的節(jié)點(diǎn)的發(fā)射半徑，這也加劇了網(wǎng)絡(luò)中節(jié)點(diǎn)的最大干擾值擴(kuò)大。
如圖1所示，由文獻(xiàn)［7］指出最近鄰算法產(chǎn)生的拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)中受到的最大的干擾達(dá)到n-2∈n。顯然，一個(gè)節(jié)點(diǎn)在有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，在最壞的情況下，受到除已的其他節(jié)點(diǎn)干擾，即干擾值為n-1，可見(jiàn)，最近鄰算法在一維指數(shù)鏈上干擾優(yōu)化的改進(jìn)效果不如人意。
圖1 最近鄰算法構(gòu)建拓?fù)淇刂频倪^(guò)程
3 干擾模型要素
根據(jù)無(wú)線傳感器網(wǎng)絡(luò)的特性，本文延續(xù)文獻(xiàn)［7-8］模型化方法利用單位圓盤圖（Unit Disk Graph，UDG）理論［13］進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)抽象建模。便于討論后文提出的干擾優(yōu)化拓?fù)淇刂扑惴?，本文采用無(wú)向圖中的頂點(diǎn)來(lái)模擬在監(jiān)測(cè)區(qū)域投放的傳感器節(jié)點(diǎn)，圖中任意2點(diǎn)存在的邊作為任意2個(gè)傳感器節(jié)點(diǎn)直接通信即一跳距離的依據(jù)。
3.1 單位圓盤圖
在UDG圖G=（V，E）中，V為圖G中頂點(diǎn)的集合，E為圖G的任意頂點(diǎn)存在邊的集合。V中的每個(gè)頂點(diǎn)都有以該頂點(diǎn)為中心的等半徑的圓一一對(duì)應(yīng)，假設(shè)所有節(jié)點(diǎn)具有相同的通信半徑上限r(nóng)max，當(dāng)且僅當(dāng)u頂點(diǎn)和v頂點(diǎn)之間的歐氏距離小于等于rmax時(shí)，則e（u，v）∈E。UDG圖頂點(diǎn)的通信半徑r，一般指定為單位1，關(guān)系數(shù)學(xué)表達(dá)式如下：
根據(jù)上述UDG圖的定義，假定UDG圖G=（u，v）為無(wú)線傳感器網(wǎng)絡(luò)的抽象模型，并設(shè)定無(wú)線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)的傳輸功率是可調(diào)節(jié)的，其有效值區(qū)間是［0，MaxPower］，其中，MaxPower代表了節(jié)點(diǎn)傳輸功率的上限值。
3.2 模型字符
為更簡(jiǎn)潔明了描述本文要點(diǎn)，將使用以下模型字符進(jìn)行定義：
（1）Nu表示結(jié)果拓?fù)鋱DT中u節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合，即在結(jié)果拓?fù)鋱DT中與u只有一跳距離的頂點(diǎn)的集合。
（2）ru表示結(jié)果拓?fù)鋱DT中u節(jié)點(diǎn)的通信半徑，ru=maxv∈Nu｛|u，v|｝，其中，|u，v|指的是u節(jié)點(diǎn)與v節(jié)點(diǎn)之間的歐氏距離。
（3）D（u，ru）表示以u(píng)為圓盤中心ru為通信半徑所覆蓋的節(jié)點(diǎn)的集合，為方便算法展開(kāi)分析，這里不考慮節(jié)點(diǎn)自身覆蓋的情況。
（4）本文采用基于接收者的干擾模型，RI（u）表示u節(jié)點(diǎn)對(duì)于根據(jù)拓?fù)淇刂频玫阶罱K的拓?fù)鋱DT=（V，E'），節(jié)點(diǎn)受到干擾是這樣定義的：
如圖2所示，每個(gè)節(jié)點(diǎn)所選用的傳輸半徑受其最遠(yuǎn)的鄰居節(jié)點(diǎn)影響，則u節(jié)點(diǎn)選用k1作為它的通信半徑，v節(jié)點(diǎn)選用k2作為通信半徑。根據(jù)式（2），可計(jì)算u，v節(jié)點(diǎn)所受到的干擾值分別為RI（u）=2，RI（v）=3。
圖2 基于接收者的干擾模型
（5）衡量結(jié)果拓?fù)鋱D的干擾值是由眾節(jié)點(diǎn)所受的干擾度最大的那個(gè)節(jié)點(diǎn)的干擾值所決定。根據(jù)3.1節(jié)中指出通信功率的上限MaxPower，則同樣的，傳感器節(jié)點(diǎn)都受限于同一個(gè)最大通信半徑值MaxRadiu，而節(jié)點(diǎn)的通信半徑取值隨著拓?fù)淇刂普{(diào)節(jié)控制在［0，MaxRadiu］區(qū)間，也就是說(shuō)，無(wú)線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)初始條件都是統(tǒng)一的，當(dāng)中的最早消耗完電量的節(jié)點(diǎn)則是受到干擾最多的那個(gè)節(jié)點(diǎn)，這也決定了當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)的生命期的長(zhǎng)度。因此，本文取圖T節(jié)點(diǎn)中RI（v）值最大者作為該算法產(chǎn)生的拓?fù)鋱D干擾：
（6）圖2中受到的平均干擾可定義為：
4 本文算法設(shè)計(jì)思想
根據(jù)上述采用的基于接收者的網(wǎng)絡(luò)拓?fù)涓蓴_模型，本文提出了一種基于干擾閾值調(diào)節(jié)的拓?fù)淇刂疲═hreshold Adaptive Topology Control，TATC）算法。TATC算法思想主要如下：
（1）建立模型：每個(gè)節(jié)點(diǎn)需要與其他節(jié)點(diǎn)進(jìn)行消息交互，收集搭建鏈路的距離即通信半徑的數(shù)據(jù)。考慮在理想狀態(tài)下，如果網(wǎng)絡(luò)中任意u，v節(jié)點(diǎn)能通過(guò)一跳距離能收到消息響應(yīng)成功，則根據(jù)式（1），它們之間的通信鏈路距離是不超過(guò)設(shè)定的單位通信半徑上限單位1，則圖G中u，v點(diǎn)中存在直接鏈路，即e（u，v）∈E。消息信息收集處理完畢，可搭建成初始拓?fù)鋱DG：
（2）初始化結(jié)構(gòu)拓?fù)鋱DT，T=（V，ETATC），ETATC= NULL。由于當(dāng)前T中邊為空集，當(dāng)前RI（T）=0；設(shè)定一個(gè)干擾閾值RI-threshold初始值為1。
（3）隨機(jī)遍歷E集合中的鏈路，對(duì)鏈路進(jìn)行預(yù)處理選擇，嘗試每一條鏈路逐步加入ETATC集合中，并計(jì)算出當(dāng)前圖T中各個(gè)節(jié)點(diǎn)RI值，從而得到RI（T）值。
（4）對(duì)當(dāng)前假設(shè)的圖T中ETATC集合中利用深度搜索算法進(jìn)行是否存在邊回路檢測(cè)，如若存在回路，則ETATC集合中將不會(huì)包含該鏈路，與此同時(shí)，E集合中也將剔除該鏈路，之后返回步驟（3），將繼續(xù)遍歷下一條鏈路。否則，執(zhí)行步驟（5）。
（5）如果加入鏈路能使RI（T）不超過(guò)當(dāng)前的RI-threshold，則該鏈路將加入ETATC集合中，與此同時(shí)，E集合中也將剔除該鏈路。
（6）遍歷完畢，延續(xù)深度搜索算法檢測(cè)圖T連通性，如果不連通，則將當(dāng)前最大干擾閾值進(jìn)行向上調(diào)整，執(zhí)行步驟（3），否則執(zhí)行步驟（7）。
（7）算法執(zhí)行完畢，得到結(jié)果拓?fù)淇刂茍DT=（V，ETATC），此時(shí)的最大干擾閾值RI-threshold則為當(dāng)前結(jié)果拓?fù)淇刂茍DT中的RI（T）值。
5 拓?fù)浣Y(jié)構(gòu)性質(zhì)分析
TATC是一個(gè)貪心算法。在進(jìn)行拓?fù)淇刂茣r(shí)，在結(jié)果拓?fù)鋱DT中的鏈路還未達(dá)到所需時(shí)，此時(shí)，算法中設(shè)定的RI-threshold閾值參數(shù)相當(dāng)于當(dāng)前的目標(biāo)函數(shù)。把所有符合當(dāng)前的全局最大干擾閾值條件下的鏈路都會(huì)包含在ETATC集合中，前提是該鏈路的加入不造成T中有環(huán)，如果造成環(huán)，直接在初始G中丟棄該鏈路，如果符合當(dāng)前添加情況，也需在G中剔除該鏈路。繼續(xù)檢測(cè)拓?fù)鋱DT是否為連通圖為該算法的出口的關(guān)鍵，如果不為連通圖，需增大RI-threshold閾值參數(shù)，繼續(xù)上述的步驟（3）。顯而易見(jiàn)，G圖中有m條鏈路，n個(gè)節(jié)點(diǎn)，每次遍歷的是當(dāng)前G中鏈路集合。RI-threshold閾值參數(shù)在算法中逐步增加，直到圖T構(gòu)成了一個(gè)連通圖。因此，步驟（3）中需要至多遍歷RI-threshold×m次。其中，RI-threshold的取值范圍的上限是n-1，步驟（4）、步驟（5）中會(huì)剔除一些冗余的鏈路，步驟（3）再次遍歷時(shí)其鏈路集合工作負(fù)荷逐漸減輕。同理，步驟（6）對(duì)圖T的連通性需檢測(cè)RI-threshold次。其中，算法從e（u，v）=E（u，v）∈V，ETATC=｛·｝開(kāi)始，重復(fù)執(zhí)行以下的操作：在所有e（u，v）=E找到符合一條符合當(dāng)前RI-。
證明：如圖3所示，一維指數(shù)鏈上有n個(gè)節(jié)點(diǎn)按照2i倍數(shù)增長(zhǎng)分布?？捎^察到RI-threshold閾值參數(shù)變化，就會(huì)有新的節(jié)點(diǎn)與最左邊的節(jié)點(diǎn)相連，RI-threshold為1時(shí)，從左至右，v0連接v1，為2時(shí)，v2連接v3并連接v0，為3時(shí)，v4連接v0，并連接v5，v6，以此類推，當(dāng)此時(shí)的RI-threshold為RI（n）（RI（n）＞2）時(shí)，其至少能連（（RI（n）-1）+（RI（n）-2）+…+1+2）個(gè)節(jié)點(diǎn)：threshold閾值參數(shù)的邊加入集合ETATC，同時(shí)在原集合E中刪除該邊，直至ETATC中有n-1條邊，即圖T為極小連通圖。算法的時(shí)間復(fù)雜度為O（n2）。
定理 在一維指數(shù)鏈圖G，應(yīng)用TATC算法構(gòu)造拓?fù)鋱D的
圖3 一維指數(shù)鏈上本文算法產(chǎn)生的結(jié)果拓?fù)浣Y(jié)構(gòu)
如圖3所示，16個(gè)節(jié)點(diǎn)的一維指數(shù)鏈，使用TATC算法所得的結(jié)構(gòu)拓?fù)鋱D中產(chǎn)生的最大干擾RI（T）=5，而根據(jù)本文第2節(jié)中指出的最近鄰算法則在該鏈路上產(chǎn)生的RI（T）=14。
6 性能仿真與分析
為評(píng)估TATC算法的有效性，根據(jù)文獻(xiàn)［8］所介紹的指數(shù)鏈特征采用UDG模型分別構(gòu)建一維指數(shù)鏈以及二維指數(shù)鏈的初始拓?fù)浣Y(jié)構(gòu)。
如圖4、圖5所示，橫坐標(biāo)表示當(dāng)前一維指數(shù)鏈網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，縱坐標(biāo)分別表示當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)的最大的干擾值、網(wǎng)絡(luò)節(jié)點(diǎn)的平均干擾值。圖中比較了最近鄰算法以及本文算法在一維指數(shù)鏈產(chǎn)生的拓?fù)鋱D中節(jié)點(diǎn)中的最大干擾值以及平均干擾值。與最近鄰算法相比，TATC算法顯著減小了網(wǎng)絡(luò)中節(jié)點(diǎn)的最大干擾值、平均干擾值，而且隨著節(jié)點(diǎn)數(shù)的增加，拓?fù)淇刂坪蟮耐負(fù)鋱D的最大干擾、平均干擾增長(zhǎng)幅度較慢。
圖4 一維指數(shù)鏈網(wǎng)絡(luò)中的最大干擾值比較
圖5 一維指數(shù)鏈網(wǎng)絡(luò)中的平均干擾值比較
圖6 、圖7仿真的是在區(qū)域1 000 m×1 000 m的區(qū)域中，據(jù)二維指數(shù)鏈特性［7］排布50個(gè)～400個(gè)節(jié)點(diǎn)，上述的2種算法在該網(wǎng)絡(luò)環(huán)境產(chǎn)生的拓?fù)浣Y(jié)構(gòu)圖中的節(jié)點(diǎn)的最大干擾值以及平均干擾值?？梢悦黠@看到，采用TATC算法的網(wǎng)絡(luò)中的最大干擾值、平均干擾值的數(shù)值優(yōu)于最近鄰算法。
圖6 二維指數(shù)鏈網(wǎng)絡(luò)中的最大干擾值比較
圖7 二維指數(shù)鏈網(wǎng)絡(luò)中的平均干擾值比較
7 結(jié)束語(yǔ)
本文設(shè)計(jì)一種基于最大干擾值閾值調(diào)節(jié)的拓?fù)淇刂扑惴?。該算法以網(wǎng)絡(luò)連通性、拓?fù)浣Y(jié)構(gòu)干擾弱化性為目標(biāo)函數(shù)，對(duì)干擾閾值不斷自適應(yīng)調(diào)節(jié)，直到構(gòu)造成所需的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，在指數(shù)鏈模型上，該算法能控制節(jié)點(diǎn)的最大干擾值在構(gòu)建拓?fù)浣Y(jié)構(gòu)中趨于緩慢增長(zhǎng)，比最近鄰算法取得了更好的干擾優(yōu)化效果。但該算法還需進(jìn)一步改善并推廣至其他網(wǎng)絡(luò)模型。今后將從網(wǎng)絡(luò)容錯(cuò)性能和適用性方面上繼續(xù)改進(jìn)該算法，以提升網(wǎng)絡(luò)的抗毀性，降低算法的局限性。
［1］ 吳成洪.無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯浚跠］.西安：西安電子科技大學(xué)，2010.
［2］ 江 勇，趙 倩.一種應(yīng)用強(qiáng)化學(xué)習(xí)的自適應(yīng)無(wú)線傳感器網(wǎng)絡(luò)路由算法［J］.小型微型計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)拓?fù)溥B通性與稀疏性研究［J］.傳感技術(shù)學(xué)報(bào)，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ò)生存期的拓?fù)淇刂扑惴ǎ跩］.計(jì)算機(jī)研究與發(fā)展，2013，50（3）：461-471.
［10］ 孫 超，尹榮榮，郝曉辰，等.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)支配集拓?fù)淇刂扑惴ǎ跩］.軟件學(xué)報(bào)，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ú)線網(wǎng)絡(luò)鄰近圖綜述［J］.軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǎ跩］.計(jì)算機(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
國(guó)家自然科學(xué)基金資助項(xiàng)目（71272144）；廣州市科技計(jì)劃基金資助項(xiàng)目（2013KP084）。
謝曉虹（1990-），女，碩士研究生，主研方向：無(wú)線傳感器網(wǎng)絡(luò)；曾碧卿，教授、博士。
2014-10-29
2014-12-23 E-m ail：zengbiqing0528@163.com
猜你喜歡
家紡“全鏈路”升級(jí)紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10 低壓配網(wǎng)拓?fù)鋱D自動(dòng)成圖關(guān)鍵技術(shù)的研究與設(shè)計(jì)電子設(shè)計(jì)工程(2023年2期)2023-01-24 12:52:12 簡(jiǎn)單拓?fù)鋱D及幾乎交錯(cuò)鏈環(huán)補(bǔ)中的閉曲面數(shù)學(xué)年刊A輯(中文版)(2022年1期)2022-08-20 08:50:22 天空地一體化網(wǎng)絡(luò)多中繼鏈路自適應(yīng)調(diào)度技術(shù)移動(dòng)通信(2021年5期)2021-10-25 11:41:48 基于含圈非連通圖優(yōu)美性的拓?fù)鋱D密碼華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2020年1期)2020-03-16 03:14:55 基于ARM+FPGA的模塊化同步控制算法研究制造技術(shù)與機(jī)床(2017年6期)2018-01-19 02:41:07 一種優(yōu)化的基于ARM Cortex-M3電池組均衡控制算法應(yīng)用電源技術(shù)(2015年9期)2015-06-05 09:36:06 基于3G的VPDN技術(shù)在高速公路備份鏈路中的應(yīng)用中國(guó)交通信息化(2014年3期)2014-06-05 03:07:09 一種非圓旋轉(zhuǎn)工件支撐裝置控制算法組合機(jī)床與自動(dòng)化加工技術(shù)(2014年12期)2014-03-01 02:22:54 高速光纖鏈路通信HSSL的設(shè)計(jì)與實(shí)現(xiàn)自動(dòng)化與儀表(2014年10期)2014-02-26 08:21:17
謝曉虹，曾碧卿
（1.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州510631；2.華南師范大學(xué)軟件學(xué)院，廣東佛山528225）
一種干擾優(yōu)化無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴?/p>
謝曉虹1，曾碧卿2
（1.華南師范大學(xué)計(jì)算機(jī)學(xué)院，廣州510631；2.華南師范大學(xué)軟件學(xué)院，廣東佛山528225）
針對(duì)如何準(zhǔn)確度量無(wú)線傳感器網(wǎng)絡(luò)中的干擾，并構(gòu)建最小化最大干擾值拓?fù)浣Y(jié)構(gòu)的問(wèn)題，根據(jù)傳感器節(jié)點(diǎn)的特點(diǎn)以及無(wú)線通信機(jī)制，提出一種閾值調(diào)節(jié)的拓?fù)淇刂扑惴?。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)收集鄰居節(jié)點(diǎn)相關(guān)信息，同時(shí)以干擾閾值為目標(biāo)函數(shù)，選取符合當(dāng)前干擾閾值以及不會(huì)使當(dāng)前拓?fù)鋱D產(chǎn)生回路的鏈路進(jìn)行拓?fù)錁?gòu)建，直至拓?fù)溥B通，實(shí)現(xiàn)整個(gè)網(wǎng)絡(luò)中節(jié)點(diǎn)最大干擾最小化。仿真結(jié)果表明，在無(wú)線傳感器網(wǎng)絡(luò)指數(shù)鏈模型下，與最近鄰算法相比，該算法生成的拓?fù)淇刂平Y(jié)構(gòu)干擾優(yōu)化效果更優(yōu)，并能保證網(wǎng)絡(luò)的連通性及更有效地延長(zhǎng)網(wǎng)絡(luò)的生存周期。
無(wú)線傳感器網(wǎng)絡(luò)；閾值控制；指數(shù)鏈模型；干擾優(yōu)化；拓?fù)淇刂?/p>
1 概述
無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）近年來(lái)的快速發(fā)展離不開(kāi)傳感器技術(shù)、網(wǎng)絡(luò)無(wú)線通信技術(shù)、嵌入式技術(shù)、分布式信息技術(shù)以及微電子制造技術(shù)等相關(guān)關(guān)鍵技術(shù)的日益成熟。它是一種無(wú)中心節(jié)點(diǎn)的全分布系統(tǒng)，是有針對(duì)性對(duì)某個(gè)監(jiān)控區(qū)域內(nèi)進(jìn)行隨機(jī)投放的若干個(gè)傳感器節(jié)點(diǎn)自組織通過(guò)無(wú)線電信通信構(gòu)成網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點(diǎn)可根據(jù)其內(nèi)置的不同功能的傳感器，感知所在的周遭環(huán)境中人們的感興趣的數(shù)據(jù)，如溫度、紅外線、濕度、壓力、土壤成分、移動(dòng)物體的屬性等［1］。正因?yàn)闊o(wú)線傳感器網(wǎng)絡(luò)的無(wú)處不在的感知技術(shù)優(yōu)勢(shì)，它有著非常廣泛的應(yīng)用前景。在軍事領(lǐng)域、環(huán)境應(yīng)用、醫(yī)療事業(yè)、工業(yè)應(yīng)用以及商用等多個(gè)領(lǐng)域都占有意義非凡的一席之地。顯然，無(wú)線傳感器網(wǎng)絡(luò)是當(dāng)前多學(xué)科高度交叉、前沿的熱點(diǎn)研究之一。無(wú)線傳感器網(wǎng)絡(luò)中傳感器節(jié)點(diǎn)一般由數(shù)據(jù)采集模塊、數(shù)據(jù)處理和控制模塊、無(wú)線通信模塊和供電模塊組成［2］。而正因?yàn)樗陨淼奈锢硖匦砸蛩兀潆娏抗┙o［3］有限成為無(wú)線傳感器網(wǎng)絡(luò)生命期主要的瓶頸問(wèn)題之一。
早期的經(jīng)典拓?fù)淇刂扑惴ㄋ枷胫饕墙柚刂乒?jié)點(diǎn)傳輸功率或稀疏化網(wǎng)絡(luò)拓?fù)鋱D［4］，達(dá)到降低節(jié)點(diǎn)信道之間干擾的目的。近階段有一些研究者，指出機(jī)械性減少邊的數(shù)量、長(zhǎng)度及鄰節(jié)點(diǎn)度不一定就能保證節(jié)點(diǎn)之間的干擾現(xiàn)象也降低［5-7］，并就干擾模型的定義和度量方法進(jìn)行了研究。其中，定義的干擾模型有基于發(fā)送節(jié)點(diǎn)的干擾模型、基于接收節(jié)點(diǎn)的干擾模型?；诓煌母蓴_模型，文獻(xiàn)［8］指出二維及二維以上的網(wǎng)絡(luò)模型的拓?fù)淇刂聘蓴_優(yōu)化問(wèn)題已被證明屬于NP問(wèn)題。
在上述拓?fù)淇刂扑惴ǖ难芯恐?，很少有以降低全局網(wǎng)絡(luò)節(jié)點(diǎn)中的最大干擾值作為首要目標(biāo)，干擾的存在不僅會(huì)影響通信質(zhì)量，而且造成數(shù)據(jù)不斷重傳損耗電量縮短網(wǎng)絡(luò)生命周期［9］，大部分算法針對(duì)的都是節(jié)點(diǎn)分布比較均勻的網(wǎng)絡(luò)情況，而對(duì)于節(jié)點(diǎn)間非均勻分布的網(wǎng)絡(luò)情況，如指數(shù)鏈模型無(wú)線傳感器網(wǎng)絡(luò)下的干擾優(yōu)化效果甚微。本文將采用基于接收節(jié)點(diǎn)干擾模型，以干擾閾值作為重要考慮因素，以最小化最大干擾值、網(wǎng)絡(luò)連通性為算法首要目標(biāo)，對(duì)一維指數(shù)鏈模型的無(wú)線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)、節(jié)點(diǎn)傳輸半徑和網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)、節(jié)點(diǎn)所受的干擾進(jìn)行研究，設(shè)計(jì)一種啟發(fā)式算法，并將其算法思想沿用至二維網(wǎng)絡(luò)模型中，保證其網(wǎng)絡(luò)連通性的同時(shí)達(dá)到優(yōu)化最大干擾值的目的。
2 相關(guān)工作
功率控制［10］是研究無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂浦匾较蛑唬β士刂浦傅氖呛侠淼卦O(shè)置或動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的傳輸半徑功率，在保證整個(gè)網(wǎng)絡(luò)的連通的同時(shí)，弱化節(jié)點(diǎn)間的相互干擾［11-13］，并達(dá)到高效節(jié)能、延長(zhǎng)網(wǎng)絡(luò)生命期的目的。文獻(xiàn)［7］指出包含最近鄰居的節(jié)點(diǎn)算法（下文簡(jiǎn)稱為最近鄰算法）在指數(shù)鏈模型上的干擾優(yōu)化效果不甚理想。在一維指數(shù)鏈上若有n個(gè)節(jié)點(diǎn)以2的指數(shù)倍的距離相隔進(jìn)行排布，由于最近鄰算法的算法特性，會(huì)將構(gòu)成網(wǎng)絡(luò)中的最短路徑的鏈路保留下來(lái)，以減少鏈路開(kāi)銷。而一維指數(shù)鏈的特性會(huì)使得新加入每一條的連接增大原先最右邊的節(jié)點(diǎn)的發(fā)射半徑，這也加劇了網(wǎng)絡(luò)中節(jié)點(diǎn)的最大干擾值擴(kuò)大。
如圖1所示，由文獻(xiàn)［7］指出最近鄰算法產(chǎn)生的拓?fù)浣Y(jié)構(gòu)節(jié)點(diǎn)中受到的最大的干擾達(dá)到n-2∈n。顯然，一個(gè)節(jié)點(diǎn)在有n個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò)中，在最壞的情況下，受到除已的其他節(jié)點(diǎn)干擾，即干擾值為n-1，可見(jiàn)，最近鄰算法在一維指數(shù)鏈上干擾優(yōu)化的改進(jìn)效果不如人意。
圖1 最近鄰算法構(gòu)建拓?fù)淇刂频倪^(guò)程
3 干擾模型要素
根據(jù)無(wú)線傳感器網(wǎng)絡(luò)的特性，本文延續(xù)文獻(xiàn)［7-8］模型化方法利用單位圓盤圖（Unit Disk Graph，UDG）理論［13］進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)抽象建模。便于討論后文提出的干擾優(yōu)化拓?fù)淇刂扑惴?，本文采用無(wú)向圖中的頂點(diǎn)來(lái)模擬在監(jiān)測(cè)區(qū)域投放的傳感器節(jié)點(diǎn)，圖中任意2點(diǎn)存在的邊作為任意2個(gè)傳感器節(jié)點(diǎn)直接通信即一跳距離的依據(jù)。
3.1 單位圓盤圖
在UDG圖G=（V，E）中，V為圖G中頂點(diǎn)的集合，E為圖G的任意頂點(diǎn)存在邊的集合。V中的每個(gè)頂點(diǎn)都有以該頂點(diǎn)為中心的等半徑的圓一一對(duì)應(yīng)，假設(shè)所有節(jié)點(diǎn)具有相同的通信半徑上限r(nóng)max，當(dāng)且僅當(dāng)u頂點(diǎn)和v頂點(diǎn)之間的歐氏距離小于等于rmax時(shí)，則e（u，v）∈E。UDG圖頂點(diǎn)的通信半徑r，一般指定為單位1，關(guān)系數(shù)學(xué)表達(dá)式如下：
根據(jù)上述UDG圖的定義，假定UDG圖G=（u，v）為無(wú)線傳感器網(wǎng)絡(luò)的抽象模型，并設(shè)定無(wú)線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)的傳輸功率是可調(diào)節(jié)的，其有效值區(qū)間是［0，MaxPower］，其中，MaxPower代表了節(jié)點(diǎn)傳輸功率的上限值。
3.2 模型字符
為更簡(jiǎn)潔明了描述本文要點(diǎn)，將使用以下模型字符進(jìn)行定義：
（1）Nu表示結(jié)果拓?fù)鋱DT中u節(jié)點(diǎn)的鄰居節(jié)點(diǎn)集合，即在結(jié)果拓?fù)鋱DT中與u只有一跳距離的頂點(diǎn)的集合。
（2）ru表示結(jié)果拓?fù)鋱DT中u節(jié)點(diǎn)的通信半徑，ru=maxv∈Nu｛|u，v|｝，其中，|u，v|指的是u節(jié)點(diǎn)與v節(jié)點(diǎn)之間的歐氏距離。
（3）D（u，ru）表示以u(píng)為圓盤中心ru為通信半徑所覆蓋的節(jié)點(diǎn)的集合，為方便算法展開(kāi)分析，這里不考慮節(jié)點(diǎn)自身覆蓋的情況。
（4）本文采用基于接收者的干擾模型，RI（u）表示u節(jié)點(diǎn)對(duì)于根據(jù)拓?fù)淇刂频玫阶罱K的拓?fù)鋱DT=（V，E'），節(jié)點(diǎn)受到干擾是這樣定義的：
如圖2所示，每個(gè)節(jié)點(diǎn)所選用的傳輸半徑受其最遠(yuǎn)的鄰居節(jié)點(diǎn)影響，則u節(jié)點(diǎn)選用k1作為它的通信半徑，v節(jié)點(diǎn)選用k2作為通信半徑。根據(jù)式（2），可計(jì)算u，v節(jié)點(diǎn)所受到的干擾值分別為RI（u）=2，RI（v）=3。
圖2 基于接收者的干擾模型
（5）衡量結(jié)果拓?fù)鋱D的干擾值是由眾節(jié)點(diǎn)所受的干擾度最大的那個(gè)節(jié)點(diǎn)的干擾值所決定。根據(jù)3.1節(jié)中指出通信功率的上限MaxPower，則同樣的，傳感器節(jié)點(diǎn)都受限于同一個(gè)最大通信半徑值MaxRadiu，而節(jié)點(diǎn)的通信半徑取值隨著拓?fù)淇刂普{(diào)節(jié)控制在［0，MaxRadiu］區(qū)間，也就是說(shuō)，無(wú)線傳感器網(wǎng)絡(luò)中的傳感器節(jié)點(diǎn)初始條件都是統(tǒng)一的，當(dāng)中的最早消耗完電量的節(jié)點(diǎn)則是受到干擾最多的那個(gè)節(jié)點(diǎn)，這也決定了當(dāng)前無(wú)線傳感器網(wǎng)絡(luò)的生命期的長(zhǎng)度。因此，本文取圖T節(jié)點(diǎn)中RI（v）值最大者作為該算法產(chǎn)生的拓?fù)鋱D干擾：
（6）圖2中受到的平均干擾可定義為：
4 本文算法設(shè)計(jì)思想
根據(jù)上述采用的基于接收者的網(wǎng)絡(luò)拓?fù)涓蓴_模型，本文提出了一種基于干擾閾值調(diào)節(jié)的拓?fù)淇刂疲═hreshold Adaptive Topology Control，TATC）算法。TATC算法思想主要如下：
（1）建立模型：每個(gè)節(jié)點(diǎn)需要與其他節(jié)點(diǎn)進(jìn)行消息交互，收集搭建鏈路的距離即通信半徑的數(shù)據(jù)。考慮在理想狀態(tài)下，如果網(wǎng)絡(luò)中任意u，v節(jié)點(diǎn)能通過(guò)一跳距離能收到消息響應(yīng)成功，則根據(jù)式（1），它們之間的通信鏈路距離是不超過(guò)設(shè)定的單位通信半徑上限單位1，則圖G中u，v點(diǎn)中存在直接鏈路，即e（u，v）∈E。消息信息收集處理完畢，可搭建成初始拓?fù)鋱DG：
（2）初始化結(jié)構(gòu)拓?fù)鋱DT，T=（V，ETATC），ETATC= NULL。由于當(dāng)前T中邊為空集，當(dāng)前RI（T）=0；設(shè)定一個(gè)干擾閾值RI-threshold初始值為1。
（3）隨機(jī)遍歷E集合中的鏈路，對(duì)鏈路進(jìn)行預(yù)處理選擇，嘗試每一條鏈路逐步加入ETATC集合中，并計(jì)算出當(dāng)前圖T中各個(gè)節(jié)點(diǎn)RI值，從而得到RI（T）值。
（4）對(duì)當(dāng)前假設(shè)的圖T中ETATC集合中利用深度搜索算法進(jìn)行是否存在邊回路檢測(cè)，如若存在回路，則ETATC集合中將不會(huì)包含該鏈路，與此同時(shí)，E集合中也將剔除該鏈路，之后返回步驟（3），將繼續(xù)遍歷下一條鏈路。否則，執(zhí)行步驟（5）。
（5）如果加入鏈路能使RI（T）不超過(guò)當(dāng)前的RI-threshold，則該鏈路將加入ETATC集合中，與此同時(shí)，E集合中也將剔除該鏈路。
（6）遍歷完畢，延續(xù)深度搜索算法檢測(cè)圖T連通性，如果不連通，則將當(dāng)前最大干擾閾值進(jìn)行向上調(diào)整，執(zhí)行步驟（3），否則執(zhí)行步驟（7）。
（7）算法執(zhí)行完畢，得到結(jié)果拓?fù)淇刂茍DT=（V，ETATC），此時(shí)的最大干擾閾值RI-threshold則為當(dāng)前結(jié)果拓?fù)淇刂茍DT中的RI（T）值。
5 拓?fù)浣Y(jié)構(gòu)性質(zhì)分析
TATC是一個(gè)貪心算法。在進(jìn)行拓?fù)淇刂茣r(shí)，在結(jié)果拓?fù)鋱DT中的鏈路還未達(dá)到所需時(shí)，此時(shí)，算法中設(shè)定的RI-threshold閾值參數(shù)相當(dāng)于當(dāng)前的目標(biāo)函數(shù)。把所有符合當(dāng)前的全局最大干擾閾值條件下的鏈路都會(huì)包含在ETATC集合中，前提是該鏈路的加入不造成T中有環(huán)，如果造成環(huán)，直接在初始G中丟棄該鏈路，如果符合當(dāng)前添加情況，也需在G中剔除該鏈路。繼續(xù)檢測(cè)拓?fù)鋱DT是否為連通圖為該算法的出口的關(guān)鍵，如果不為連通圖，需增大RI-threshold閾值參數(shù)，繼續(xù)上述的步驟（3）。顯而易見(jiàn)，G圖中有m條鏈路，n個(gè)節(jié)點(diǎn)，每次遍歷的是當(dāng)前G中鏈路集合。RI-threshold閾值參數(shù)在算法中逐步增加，直到圖T構(gòu)成了一個(gè)連通圖。因此，步驟（3）中需要至多遍歷RI-threshold×m次。其中，RI-threshold的取值范圍的上限是n-1，步驟（4）、步驟（5）中會(huì)剔除一些冗余的鏈路，步驟（3）再次遍歷時(shí)其鏈路集合工作負(fù)荷逐漸減輕。同理，步驟（6）對(duì)圖T的連通性需檢測(cè)RI-threshold次。其中，算法從e（u，v）=E（u，v）∈V，ETATC=｛·｝開(kāi)始，重復(fù)執(zhí)行以下的操作：在所有e（u，v）=E找到符合一條符合當(dāng)前RI-。
證明：如圖3所示，一維指數(shù)鏈上有n個(gè)節(jié)點(diǎn)按照2i倍數(shù)增長(zhǎng)分布?？捎^察到RI-threshold閾值參數(shù)變化，就會(huì)有新的節(jié)點(diǎn)與最左邊的節(jié)點(diǎn)相連，RI-threshold為1時(shí)，從左至右，v0連接v1，為2時(shí)，v2連接v3并連接v0，為3時(shí)，v4連接v0，并連接v5，v6，以此類推，當(dāng)此時(shí)的RI-threshold為RI（n）（RI（n）＞2）時(shí)，其至少能連（（RI（n）-1）+（RI（n）-2）+…+1+2）個(gè)節(jié)點(diǎn)：threshold閾值參數(shù)的邊加入集合ETATC，同時(shí)在原集合E中刪除該邊，直至ETATC中有n-1條邊，即圖T為極小連通圖。算法的時(shí)間復(fù)雜度為O（n2）。
定理 在一維指數(shù)鏈圖G，應(yīng)用TATC算法構(gòu)造拓?fù)鋱D的
圖3 一維指數(shù)鏈上本文算法產(chǎn)生的結(jié)果拓?fù)浣Y(jié)構(gòu)
如圖3所示，16個(gè)節(jié)點(diǎn)的一維指數(shù)鏈，使用TATC算法所得的結(jié)構(gòu)拓?fù)鋱D中產(chǎn)生的最大干擾RI（T）=5，而根據(jù)本文第2節(jié)中指出的最近鄰算法則在該鏈路上產(chǎn)生的RI（T）=14。
6 性能仿真與分析
為評(píng)估TATC算法的有效性，根據(jù)文獻(xiàn)［8］所介紹的指數(shù)鏈特征采用UDG模型分別構(gòu)建一維指數(shù)鏈以及二維指數(shù)鏈的初始拓?fù)浣Y(jié)構(gòu)。
如圖4、圖5所示，橫坐標(biāo)表示當(dāng)前一維指數(shù)鏈網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)，縱坐標(biāo)分別表示當(dāng)前網(wǎng)絡(luò)中節(jié)點(diǎn)的最大的干擾值、網(wǎng)絡(luò)節(jié)點(diǎn)的平均干擾值。圖中比較了最近鄰算法以及本文算法在一維指數(shù)鏈產(chǎn)生的拓?fù)鋱D中節(jié)點(diǎn)中的最大干擾值以及平均干擾值。與最近鄰算法相比，TATC算法顯著減小了網(wǎng)絡(luò)中節(jié)點(diǎn)的最大干擾值、平均干擾值，而且隨著節(jié)點(diǎn)數(shù)的增加，拓?fù)淇刂坪蟮耐負(fù)鋱D的最大干擾、平均干擾增長(zhǎng)幅度較慢。
圖4 一維指數(shù)鏈網(wǎng)絡(luò)中的最大干擾值比較
圖5 一維指數(shù)鏈網(wǎng)絡(luò)中的平均干擾值比較
圖6 、圖7仿真的是在區(qū)域1 000 m×1 000 m的區(qū)域中，據(jù)二維指數(shù)鏈特性［7］排布50個(gè)～400個(gè)節(jié)點(diǎn)，上述的2種算法在該網(wǎng)絡(luò)環(huán)境產(chǎn)生的拓?fù)浣Y(jié)構(gòu)圖中的節(jié)點(diǎn)的最大干擾值以及平均干擾值?？梢悦黠@看到，采用TATC算法的網(wǎng)絡(luò)中的最大干擾值、平均干擾值的數(shù)值優(yōu)于最近鄰算法。
圖6 二維指數(shù)鏈網(wǎng)絡(luò)中的最大干擾值比較
圖7 二維指數(shù)鏈網(wǎng)絡(luò)中的平均干擾值比較
7 結(jié)束語(yǔ)
本文設(shè)計(jì)一種基于最大干擾值閾值調(diào)節(jié)的拓?fù)淇刂扑惴?。該算法以網(wǎng)絡(luò)連通性、拓?fù)浣Y(jié)構(gòu)干擾弱化性為目標(biāo)函數(shù)，對(duì)干擾閾值不斷自適應(yīng)調(diào)節(jié)，直到構(gòu)造成所需的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。實(shí)驗(yàn)結(jié)果表明，在指數(shù)鏈模型上，該算法能控制節(jié)點(diǎn)的最大干擾值在構(gòu)建拓?fù)浣Y(jié)構(gòu)中趨于緩慢增長(zhǎng)，比最近鄰算法取得了更好的干擾優(yōu)化效果。但該算法還需進(jìn)一步改善并推廣至其他網(wǎng)絡(luò)模型。今后將從網(wǎng)絡(luò)容錯(cuò)性能和適用性方面上繼續(xù)改進(jìn)該算法，以提升網(wǎng)絡(luò)的抗毀性，降低算法的局限性。
［1］ 吳成洪.無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂蒲芯浚跠］.西安：西安電子科技大學(xué)，2010.
［2］ 江 勇，趙 倩.一種應(yīng)用強(qiáng)化學(xué)習(xí)的自適應(yīng)無(wú)線傳感器網(wǎng)絡(luò)路由算法［J］.小型微型計(jì)算機(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ú)線傳感器網(wǎng)絡(luò)拓?fù)溥B通性與稀疏性研究［J］.傳感技術(shù)學(xué)報(bào)，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ò)生存期的拓?fù)淇刂扑惴ǎ跩］.計(jì)算機(jī)研究與發(fā)展，2013，50（3）：461-471.
［10］ 孫 超，尹榮榮，郝曉辰，等.異構(gòu)無(wú)線傳感器網(wǎng)絡(luò)支配集拓?fù)淇刂扑惴ǎ跩］.軟件學(xué)報(bào)，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ú)線網(wǎng)絡(luò)鄰近圖綜述［J］.軟件學(xué)報(bào)，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ú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴ǎ跩］.計(jì)算機(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
國(guó)家自然科學(xué)基金資助項(xiàng)目（71272144）；廣州市科技計(jì)劃基金資助項(xiàng)目（2013KP084）。
謝曉虹（1990-），女，碩士研究生，主研方向：無(wú)線傳感器網(wǎng)絡(luò)；曾碧卿，教授、博士。
2014-10-29
2014-12-23 E-m ail：zengbiqing0528@163.com
猜你喜歡
紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10
電子設(shè)計(jì)工程(2023年2期)2023-01-24 12:52:12
數(shù)學(xué)年刊A輯(中文版)(2022年1期)2022-08-20 08:50:22
移動(dòng)通信(2021年5期)2021-10-25 11:41:48
華東師范大學(xué)學(xué)報(bào)(自然科學(xué)版)(2020年1期)2020-03-16 03:14:55
制造技術(shù)與機(jī)床(2017年6期)2018-01-19 02:41:07
電源技術(shù)(2015年9期)2015-06-05 09:36:06
中國(guó)交通信息化(2014年3期)2014-06-05 03:07:09
組合機(jī)床與自動(dòng)化加工技術(shù)(2014年12期)2014-03-01 02:22:54
自動(dòng)化與儀表(2014年10期)2014-02-26 08:21:17
