本站小編為你精心準(zhǔn)備了無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴▍⒖挤段模高@些范文能點(diǎn)燃您思維的火花，激發(fā)您的寫(xiě)作靈感。歡迎深入閱讀并收藏。

無(wú)線傳感器網(wǎng)絡(luò)(WirelessSensorNetwork，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)物體的屬性等。正因?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ú)線通信模塊和供電模塊組成。而正因?yàn)樗陨淼奈锢硖匦砸蛩兀潆娏抗┙o有限成為無(wú)線傳感器網(wǎng)絡(luò)生命期主要的瓶頸問(wèn)題之一。早期的經(jīng)典拓?fù)淇刂扑惴ㄋ枷胫饕墙柚刂乒?jié)點(diǎn)傳輸功率或稀疏化網(wǎng)絡(luò)拓?fù)?/a>圖，達(dá)到降低節(jié)點(diǎn)信道之間干擾的目的。近階段有一些研究者，指出機(jī)械性減少邊的數(shù)量、長(zhǎng)度及鄰節(jié)點(diǎn)度不一定就能保證節(jié)點(diǎn)之間的干擾現(xiàn)象也降低，并就干擾模型的定義和度量方法進(jìn)行了研究。其中，定義的干擾模型有基于發(fā)送節(jié)點(diǎn)的干擾模型、基于接收節(jié)點(diǎn)的干擾模型。基于不同的干擾模型，文獻(xiàn)［8］指出二維及二維以上的網(wǎng)絡(luò)模型的拓?fù)淇刂聘蓴_優(yōu)化問(wèn)題已被證明屬于NP問(wèn)題。在上述拓?fù)?a href="http://www.gaoruijun.cn/txcb/wltplw/683630.html" target="_blank">控制算法的研究中，很少有以降低全局網(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)工作

功率控制是研究無(wú)線傳感器網(wǎng)絡(luò)拓?fù)淇刂浦匾较蛑唬β士刂浦傅氖呛侠淼卦O(shè)置或動(dòng)態(tài)調(diào)整節(jié)點(diǎn)的傳輸半徑功率，在保證整個(gè)網(wǎng)絡(luò)的連通的同時(shí)，弱化節(jié)點(diǎn)間的相互干擾，并達(dá)到高效節(jié)能、延長(zhǎng)網(wǎng)絡(luò)生命期的目的。文獻(xiàn)［7］指出包含最近鄰居的節(jié)點(diǎn)算法(下文簡(jiǎn)稱(chēng)為最近鄰算法)在指數(shù)鏈模型上的干擾優(yōu)化效果不甚理想。在一維指數(shù)鏈上若有n個(gè)節(jié)點(diǎn)以2的指數(shù)倍的距離相隔進(jìn)行排布，由于最近鄰算法的算法特性，會(huì)將構(gòu)成網(wǎng)絡(luò)中的最短路徑的鏈路保留下來(lái)，以減少鏈路開(kāi)銷(xiāo)。而一維指數(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)效果不如人意。

3干擾模型要素

根據(jù)無(wú)線傳感器網(wǎng)絡(luò)的特性，本文延續(xù)文獻(xiàn)［7-8］模型化方法利用單位圓盤(pán)圖(UnitDiskGraph，UDG)理論］進(jìn)行無(wú)線傳感器網(wǎng)絡(luò)抽象建模。便于討論后文提出的干擾優(yōu)化拓?fù)淇刂扑惴ǎ疚牟捎脽o(wú)向圖中的頂點(diǎn)來(lái)模擬在監(jiān)測(cè)區(qū)域投放的傳感器節(jié)點(diǎn)，圖中任意2點(diǎn)存在的邊作為任意2個(gè)傳感器節(jié)點(diǎn)直接通信即一跳距離的依據(jù)。

3．1單位圓盤(pán)圖在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。根據(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)為圓盤(pán)中心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)受到干擾是這樣定義。(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)度。

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

根據(jù)上述采用的基于接收者的網(wǎng)絡(luò)拓?fù)涓蓴_模型，本文提出了一種基于干擾閾值調(diào)節(jié)的拓?fù)淇刂?ThresholdAdaptiveTopologyControl，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。(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-threshold閾值參數(shù)的邊加入集合ETATC，同時(shí)在原集合E中刪除該邊，直至ETATC中有n－1條邊，即圖T為極小連通圖。算法的時(shí)間復(fù)雜度為O(n2)。如圖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)幅度較慢。圖6、圖7仿真的是在區(qū)域1000m×1000m的區(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)于最近鄰算法。

7結(jié)束語(yǔ)

本文設(shè)計(jì)一種基于最大干擾值閾值調(diào)節(jié)的拓?fù)淇刂扑惴āＴ撍惴ㄒ跃W(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ò)的抗毀性，降低算法的局限性。

作者：謝曉虹 曾碧卿 單位：華南師范大學(xué)計(jì)算機(jī)學(xué)院 華南師范大學(xué)軟件學(xué)院