基于物理干擾模型的WSN拓?fù)淇刂扑惴?/h1>
2014-08-05 04:27:31李玉民禹繼國萬勝利
計(jì)算機(jī)工程 2014年5期
李玉民，禹繼國，萬勝利
(曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，山東 日照276826)
基于物理干擾模型的WSN拓?fù)淇刂扑惴?/p>
李玉民，禹繼國，萬勝利
(曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，山東 日照276826)
拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)研究中的重要問題?，F(xiàn)有的大多數(shù)關(guān)于拓?fù)淇刂频墓ぷ骷杏谌绾谓档湍芎?，但是沒有考慮干擾帶來的影響。針對(duì)網(wǎng)絡(luò)容量的最大化問題，提出一種在信號(hào)干擾信噪比模型下的拓?fù)淇刂扑惴≒LTCA。該算法無需任何節(jié)點(diǎn)的位置信息，通過計(jì)算3跳以內(nèi)的前向和后向列表來構(gòu)建拓?fù)?。在PLTCA算法中，采用功率控制技術(shù)，節(jié)點(diǎn)通過改變發(fā)射功率或者發(fā)射方向選擇自己的鄰居節(jié)點(diǎn)，從而控制網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。通過理論分析對(duì)算法的連通性進(jìn)行論證。仿真結(jié)果表明，PLTCA算法在保證網(wǎng)絡(luò)連通性的基礎(chǔ)上，減少了網(wǎng)絡(luò)總體的能量損耗，與MaxSR算法相比，節(jié)點(diǎn)的平均鏈路能量損耗減少10%～20%。
無線自組網(wǎng)；信號(hào)干擾信噪比；無線傳感器網(wǎng)絡(luò)；拓?fù)淇刂疲荒芰繐p耗；連通性
1 概述
無線傳感器網(wǎng)絡(luò)(Wireless Sensor Net work, WS N)有著廣闊的應(yīng)用前景，它在國家安全、環(huán)境監(jiān)測(cè)、交通管理、空間探索等領(lǐng)域有著重大的應(yīng)用價(jià)值，引起了各界的廣泛關(guān)注。拓?fù)淇刂萍夹g(shù)是無線傳感器網(wǎng)絡(luò)中最重要的技術(shù)之一。在由無線傳感器網(wǎng)絡(luò)生成的網(wǎng)絡(luò)拓?fù)渲校梢灾苯油ㄐ诺?個(gè)節(jié)點(diǎn)之間存在一條拓?fù)溥?。如果沒有拓?fù)淇刂?，所有?jié)點(diǎn)都會(huì)以最大無線傳輸功率工作。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的無線信號(hào)將覆蓋大量其他節(jié)點(diǎn)，造成無線信號(hào)沖突頻繁，影響節(jié)點(diǎn)的無線通信質(zhì)量，降低網(wǎng)絡(luò)的吞吐率。另一方面，在生成的網(wǎng)絡(luò)拓?fù)渲袑⒋嬖诖罅康倪?，從而?dǎo)致網(wǎng)絡(luò)拓?fù)湫畔⒘看?，路由?jì)算復(fù)雜，浪費(fèi)了寶貴的計(jì)算資源。因此，需要研究無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂茊栴}，在維持拓?fù)淠承┤中再|(zhì)的前提下，通過調(diào)整節(jié)點(diǎn)的發(fā)送功率來延長網(wǎng)絡(luò)生命周期，提高網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)干擾，節(jié)約節(jié)點(diǎn)資源。
在無線傳感器網(wǎng)絡(luò)中，如何在消耗最低功率的前提下確定每個(gè)節(jié)點(diǎn)的傳輸功率以維持網(wǎng)絡(luò)連通性，提高空間重用是一個(gè)重要的問題[1]。文獻(xiàn)[2]提出一種拓?fù)淇刂扑惴≧TC。該算法基于RSSI均值計(jì)算節(jié)點(diǎn)間雙向路徑損耗，從而判斷兩節(jié)點(diǎn)間是否存在每跳通信鏈路代價(jià)都小于直接通信鏈路代價(jià)的兩跳路徑，以構(gòu)建局部優(yōu)化拓?fù)洹?/p>
本文提出一種集中式算法，該算法是一種基于物理模型的拓?fù)淇刂扑惴?Path Lo ss Topology C ontrol Al gorithm, PLTCA)。
2 相關(guān)工作
無線傳感器網(wǎng)絡(luò)通常具有大規(guī)模、自組織、隨機(jī)部署、傳感器節(jié)點(diǎn)資源有限、網(wǎng)絡(luò)拓?fù)鋾r(shí)常發(fā)生變化的特點(diǎn)[3]。這些特點(diǎn)反映了拓?fù)淇刂茊栴}的重要性。拓?fù)淇刂频哪繕?biāo)是維持無線自組網(wǎng)的性能(例如，連通性和功率效率)。在現(xiàn)存的拓?fù)淇刂扑惴ㄖ形墨I(xiàn)[4]做了一個(gè)全面的研究。它分為2個(gè)基本的類別：鏈路控制[5]和節(jié)點(diǎn)控制[6]。在鏈路控制中，節(jié)點(diǎn)對(duì)不同的接收器使用不同的發(fā)射功率。相反，在節(jié)點(diǎn)控制中，節(jié)點(diǎn)對(duì)不同的接收器使用相同的發(fā)射功率。節(jié)點(diǎn)控制簡化了鄰居的管理和相關(guān)的MAC控制，鏈路控制會(huì)節(jié)省很多能量。為了在有損耗的無線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)可靠的拓?fù)?，提出了ATPC算法設(shè)計(jì)，僅僅是為了維持每跳的鏈路質(zhì)量[7]。它不能在多跳網(wǎng)絡(luò)上實(shí)現(xiàn)路徑質(zhì)量的需求，也不能給不同的質(zhì)量標(biāo)準(zhǔn)靈活地配置一個(gè)網(wǎng)絡(luò)。在文獻(xiàn)[8]中，ART協(xié)議是在室內(nèi)環(huán)境中基于鏈路測(cè)量值的拓?fù)淇刂?。在另一方面，?shí)驗(yàn)中的結(jié)果通過采用CTC維持現(xiàn)實(shí)的和真實(shí)的鏈路模型。文獻(xiàn)[9]研究了傳統(tǒng)網(wǎng)絡(luò)模型的局限性，并且在物理模型下分析了拓?fù)淇刂浦墟溌氛{(diào)度的影響。文獻(xiàn)[10]提出局部算法。文獻(xiàn)[11]提出一種面向?qū)嶋H無線環(huán)境應(yīng)用且無需任何位置信息的拓?fù)淇刂扑惴?。本文提出的算法是基于物理干擾模型的拓?fù)淇刂扑惴ā?/p>
3 WSN的干擾模型和網(wǎng)絡(luò)模型
3.1 物理干擾模型
大規(guī)模的路徑損耗被用來描述信號(hào)是如何沿著傳輸路徑變?nèi)醯?。讓gu, v作為節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的通道增益(它通常假設(shè)為恒定的互不依靠的距離)，接收功率表示為：
其中，α是路徑損耗指數(shù)，α的價(jià)值范圍在2～4之間，取決于使用的傳播模型(例α=2是自由空間模型)。一個(gè)傳輸活動(dòng)是否成功取決于2個(gè)因素，也就是接收靈敏度和信號(hào)干擾信噪比(Signal to Interference plus Noise Ratio, SINR)。具體地說，是讓RXmin作為接收器的臨界值來正確地解碼接收信號(hào)，SINR的臨界值為β。一個(gè)信號(hào)可以成功地接收和解碼只要滿足以下2個(gè)公式：
3.2 無線傳感器網(wǎng)絡(luò)模型
在無線傳感器網(wǎng)絡(luò)中假設(shè)每個(gè)節(jié)點(diǎn)u(u∈V)的最大發(fā)射功率pmax。無線傳感器網(wǎng)絡(luò)中的任意節(jié)點(diǎn)u是有向圖G( V, E)的頂點(diǎn)，圖G中的節(jié)點(diǎn)u和v通過一條從u到v的邊連接。如果(u, v)∈E，則(v, u)∈E，G為所有節(jié)點(diǎn)以最大功率發(fā)射生成的初始拓?fù)鋱D。在圖G( V, E)中，pmin(u, v)表示節(jié)點(diǎn)u到達(dá)鄰居節(jié)點(diǎn)v的最小功率，此時(shí)v的接收信號(hào)強(qiáng)度為rssv。用CG(u, v)表示節(jié)點(diǎn)u以功率pmin(u, v)發(fā)射時(shí)的路徑損耗，并將CG(u, v)作為權(quán)值賦給邊(u, v)，其中(u, v)∈E。如果圖G是連通的，則節(jié)點(diǎn)u和v之間必然存在并且至少存在一條鏈路：
則該鏈路的路徑損耗可表示為：
4 算法及其實(shí)現(xiàn)
4.1 無線傳感器拓?fù)淇刂扑惴枋?/p>
相關(guān)定義如下：
(1)pmin(u, v)表示從節(jié)點(diǎn)u到達(dá)節(jié)點(diǎn)v所需的最小發(fā)射功率。
(2)C( u, v)表示路徑損耗。對(duì)于每個(gè)有序節(jié)點(diǎn)對(duì)u和v，定義一個(gè)關(guān)聯(lián)組C( u, v)=(α1, α2)，α1=IDv；α2= pmin(u, v)-rssv。其中，α1是節(jié)點(diǎn)v的編號(hào)；α2表示節(jié)點(diǎn)u以最小功率pmin(u, v)發(fā)射到v的路徑損耗值。如果α2＜α2'或者α2=α2'且α1＜α2'，則(α1, α2)＜(α', α')。
12
(3)forwardlist和backwardlist表示路徑損耗列表，也就是說前向路徑損耗列表和后向路徑損耗列表。forwardlist( u)記錄了節(jié)點(diǎn)u與它的所有鄰居節(jié)點(diǎn)直接通信的關(guān)聯(lián)組C( u, v)=(α1, α2)，u, v∈V，backwardlist( u)記錄了u的所有鄰居節(jié)點(diǎn)與u直接通信的關(guān)聯(lián)組C( u, v)= (α', α')，u, v∈V且v∈N( u)。其中，N( u)表示的是節(jié)
12 點(diǎn)u的鄰居集。假設(shè)每個(gè)節(jié)點(diǎn)u有k個(gè)鄰居節(jié)點(diǎn)，則它具有k個(gè)發(fā)射功率等級(jí)，其最大功率為pmax，最小功率為pmin，第k個(gè)鄰居通信的發(fā)射功率為pk。各節(jié)點(diǎn)依次以計(jì)算好的功率pk廣播包含當(dāng)前發(fā)射功率pk和節(jié)點(diǎn)ID的HELLO報(bào)文，每個(gè)節(jié)點(diǎn)根據(jù)接收的報(bào)文編制前向和后向路徑損耗列表。
算法描述如下：
Step1 節(jié)點(diǎn)u在初始時(shí)以最大功率工作，并廣播探測(cè)拓?fù)涞恼?qǐng)求信息，請(qǐng)求信息中包含節(jié)點(diǎn)的ID、節(jié)點(diǎn)的位置和最大功率等信息。節(jié)點(diǎn)v收到請(qǐng)求信息后，判斷是否大于最小接收功率。根據(jù)SINR物理模型判斷v是否能夠接收u的消息。如果節(jié)點(diǎn)v能收到u的消息，則將v加到N( u)中。
Step2 確定k個(gè)發(fā)射功率，每個(gè)節(jié)點(diǎn)以設(shè)定的最大功率廣播自身的ID號(hào)和位置信息。根據(jù)接收者的消息通過式(1)確定k個(gè)發(fā)送功率。
Step3 列表匯集，各節(jié)點(diǎn)依次以功率pk廣播包含當(dāng)前發(fā)射功率pk和節(jié)點(diǎn)ID的HELLO報(bào)文，每個(gè)節(jié)點(diǎn)根據(jù)接收的報(bào)文編制前向路徑損耗列表和后向路徑損耗列表。
Step4 拓?fù)浣?，每個(gè)節(jié)點(diǎn)以最大發(fā)射功率pmax向它的所有鄰居節(jié)點(diǎn)廣播前向和后向路徑損耗列表，同時(shí)也收集其各個(gè)鄰居節(jié)點(diǎn)的前向和后向路徑損耗列表。計(jì)算節(jié)點(diǎn)u和v之間小于等于3跳的前向和后向路徑，并判斷每一跳的能量消耗是否比節(jié)點(diǎn)u和v直接通信所需能量消耗小。如果u和v之間存在這樣的路徑，則從圖G中移走邊G( u, v)。
4.2 偽代碼
算法主要由4個(gè)階段組成：鄰居生成階段，功率分配階段，列表匯集階段和拓?fù)浣㈦A段。
(1)鄰居生成階段
(2)功率分配階段
假設(shè)每個(gè)節(jié)點(diǎn)u具有k個(gè)功率等級(jí)，其最大功率為pmax，最小功率為pmin，且當(dāng)前級(jí)別功率用pk表示，每個(gè)傳感器節(jié)點(diǎn)的最小接收功率假設(shè)為0.4。
偽代碼如下：
(3)列表匯集階段
各節(jié)點(diǎn)依次以功率pk廣播包含當(dāng)前發(fā)射功率pk和節(jié)點(diǎn)ID的HELLO報(bào)文，每個(gè)節(jié)點(diǎn)根據(jù)接收的報(bào)文編制前向和后向路徑損耗列表。該過程的程序偽代碼如下：
(4)拓?fù)浣㈦A段
每個(gè)節(jié)點(diǎn)以最大發(fā)射功率pmax向它的所有鄰居節(jié)點(diǎn)廣播它的前向路徑損耗列表和后向路徑損耗列表，同時(shí)也收集其各個(gè)鄰居節(jié)點(diǎn)的前向路徑損耗列表和后向路徑損耗列表。從任一節(jié)點(diǎn)u的前向路徑損耗列表中取出第一個(gè)有序?qū)( u, v)，并將C( u, v)從forwardlist( u)中刪除。構(gòu)建一個(gè)節(jié)點(diǎn)v的所有鄰居節(jié)點(diǎn)中滿足C( w, v)＜C( u, v),w∈N( v)的節(jié)點(diǎn)集合Nu(v)。從Nu(v)中任意取出ω，先判斷ω是否為u的鄰居節(jié)點(diǎn)。如果是，則判斷C( u,ω)＜ C( u, v)是否成立，如果成立，則標(biāo)志變量ftPath=True；如果ω不是u的鄰居節(jié)點(diǎn)，判斷是否存在u的鄰居節(jié)點(diǎn)z滿足條件：(C( u, z)∈forwardlist( u))&&(C( z,ω)forwardlist( z) ), z∈N( u)and z≠v 。如果成立，則ftPath= True。同樣，可以判斷是否存在從v到u的3跳或者3跳內(nèi)的后向路徑，并且每一跳的能量消耗都小于直接從v到u的路徑消耗。如果前向和后向存在這樣的路徑，則從圖中刪除邊(u,v)，該過程的程序偽碼如下：
4.3 網(wǎng)絡(luò)連通性分析
定理 如果初始圖G( V, E)連通，則執(zhí)行算法得到的拓?fù)鋱DG'( V',E')也是連通的。
證明：對(duì)于任意2個(gè)節(jié)點(diǎn)u, v∈V，由于圖G( V, E)是連通的，因此圖G( V, E)中節(jié)點(diǎn)u，v之間存在路徑p，設(shè)路徑p為：p={v0=u, v1, v2,…,vn=v}。其中，vi-1和vi( i=0,1,…,n)互為鄰居節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)之間的通信是滿足雙向性的，僅考慮前向路徑損耗。證明圖G'( V',E')是連通的，只需證明在執(zhí)行完算法后，任意2個(gè)互為鄰居的節(jié)點(diǎn)vi-1和vi( i=0,1,…,n)之間是存在通信鏈路的。執(zhí)行算法后，G'( V',E')中每個(gè)節(jié)點(diǎn)v都建立起了自己的前向路徑損耗列表forwardlist(vi)并且收集了鄰居節(jié)點(diǎn)的后向路徑損耗列表backwardlist(vi+1)，如果2個(gè)節(jié)點(diǎn)是鄰居，則前向路徑損耗列表forwardlist(vi)中一定存在C( vi, vi+1)。因此，只需證明vi和vi+1之間存在通信鏈路。假設(shè)執(zhí)行算法后vi和vi+1之間不存在通信鏈路，則邊e( vi, vi+1)一定不存在。根據(jù)算法的執(zhí)行規(guī)則，在節(jié)點(diǎn)vi+1的后向路徑損耗列表backwardlist(vi+1)中存在C(ω,vi +1)，在集合Nv(vi+1)中一定存在滿足C(ω,vi +1)＜C( vi, vi+1)的節(jié)點(diǎn)ω。那么分為以下2種情況：
(1)節(jié)點(diǎn)vi的前向路徑損耗列表forwardlist(vi)中有C( vi,ω)＜C( vi, vi +1)，ω為vi和vi+1的鄰居，且在vi和vi+1之間存在C( v,ω)＜C(ω,vi+1)，也就是說節(jié)點(diǎn)vi和節(jié)點(diǎn)vi+1之間存在通信鏈路vi→ω→vi+1。
(2)在節(jié)點(diǎn)vi的前向路徑損耗列表forwardlist(vi)中存在C( vi, z), z∈N( vi)，在z的前向路徑損耗列表forwardlist(z)中存在C( z,ω)，且滿足max(C( u, z), C( z,ω))＜C( vi, vi +1)，可見在vi和vi+1之間存在C( vi, z)＜C( z,ω)＜C( z, vi +1)，即vi和vi+1之間存在通信路徑vi→z→ω→vi+1。因此，vi和vi+1之間存在通信鏈路，與前邊的假設(shè)是相互矛盾的。所以如果初始圖G( V, E)連通，則執(zhí)行算法得到的拓?fù)鋱DG'( V',E')也是連通的。
5 仿真結(jié)果分析
PLTCA采用路徑損耗構(gòu)建網(wǎng)絡(luò)拓?fù)?，且無需節(jié)點(diǎn)的位置信息。運(yùn)用Java仿真器對(duì)PLTCA算法與MaxSR算法進(jìn)行了對(duì)比仿真。
在實(shí)驗(yàn)中，路徑損耗指數(shù)α在整個(gè)網(wǎng)絡(luò)中是相同的，取α=2。節(jié)點(diǎn)的發(fā)射功率是通過路徑損耗模型計(jì)算的，基于這種參數(shù)配置，提出了以下仿真：
方案1 將50個(gè)節(jié)點(diǎn)隨機(jī)布置在500×400的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)賦予唯一的ID號(hào)。執(zhí)行PLTCA算法得到的拓?fù)浣Y(jié)構(gòu)與執(zhí)行MaxSR[13]算法得到的拓?fù)浣Y(jié)構(gòu)進(jìn)行了對(duì)比，如圖1和圖2所示。其中，MaxSR算法執(zhí)行后鏈路數(shù)為52，執(zhí)行PLTCA算法后鏈路數(shù)為49。
圖1 P LTCA算法的執(zhí)行結(jié)果1
圖2 MaxSR算法的執(zhí)行結(jié)果1
方案2 將80個(gè)節(jié)點(diǎn)隨機(jī)布置在500×400的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)賦予唯一的ID號(hào)。執(zhí)行PLTCA算法得到的拓?fù)浣Y(jié)構(gòu)與執(zhí)行算法MaxSR的拓?fù)浣Y(jié)構(gòu)進(jìn)行對(duì)比，如圖3和圖4所示。其中，MaxSR算法執(zhí)行后鏈路數(shù)為93，執(zhí)行PLTCA算法后鏈路數(shù)為82。
圖3 P LTCA算法的執(zhí)行結(jié)果2
圖4 MaxSR算法的執(zhí)行結(jié)果2
方案3 將110個(gè)節(jié)點(diǎn)隨機(jī)布置在500×400的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)賦予唯一的ID號(hào)。執(zhí)行PLTCA算法得到的拓?fù)浣Y(jié)構(gòu)與執(zhí)行算法MaxSR的拓?fù)浣Y(jié)構(gòu)進(jìn)行了對(duì)比，如圖5和圖6所示。其中，MaxSR算法執(zhí)行后鏈路數(shù)為132，執(zhí)行PLTCA算法后鏈路數(shù)為121。
圖5 L TCA算法的執(zhí)行結(jié)果3
圖6 MaxSR算法的執(zhí)行結(jié)果3
圖7、圖8為在相同的傳感器節(jié)點(diǎn)部署條件下，分別對(duì)激活鏈路數(shù)和平均鏈路路經(jīng)損耗進(jìn)行了對(duì)比，其中，激活的鏈路指的是拓?fù)鋱D中的鏈路數(shù)，平均鏈路路經(jīng)損耗指的是所有鏈路路經(jīng)損耗的和除以鏈路數(shù)。
圖7 激活鏈路數(shù)對(duì)比
圖8 平均鏈路路徑損耗對(duì)比
通過以上仿真實(shí)驗(yàn)，對(duì)2個(gè)算法的性能結(jié)果進(jìn)行了比較。結(jié)果表明，算法PLTCA的性能較為優(yōu)越，算法PLTCA在節(jié)點(diǎn)的平均鏈路路徑損耗上優(yōu)于MaxSR算法10%～20%。物理模型下研究拓?fù)淇刂聘咏鎸?shí)情況。
6 結(jié)束語
實(shí)際的無線環(huán)境中具有多種不規(guī)則和多徑傳播現(xiàn)象，如果沒有拓?fù)淇刂扑惴?，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)將被迫使用大發(fā)射功率發(fā)送信息以確保通信和網(wǎng)絡(luò)連通。本文提出的算法并不需要任何基于位置的信息，適用于實(shí)際無線環(huán)境下的普通節(jié)點(diǎn)、異構(gòu)網(wǎng)絡(luò)，減少了網(wǎng)絡(luò)總體能量消耗，延長了網(wǎng)絡(luò)生命周期。仿真結(jié)果表明，PLTCA算法具有較好的性能。在下一步的工作中，將進(jìn)一步降低計(jì)算復(fù)雜度以及通信開銷。
[1] Hu L. A Novel Topology Control for Multihop Pac ket Radio Networks[C]//Proc. of IE EE INF OCOM’91. Mia mi, US A: [s. n.], 1991: 1084-1093.
[2] 王出航. 基于RSSI均值的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J].計(jì)算機(jī)應(yīng)用, 2012, 32(2): 352-354, 358.
[3] Akyildiz I F, Su W eilian, Sankarasubramaniam Y, et al. A Survey on Sensor Networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.
[4] Simon G. Probabilistic Wireless Network Simulator[EB/OL]. (2008-06-23). http://www.isis.vanderbilt.edu/projects/nest/prowler.
[5] Ramanathan R, Hain R. Topology Co ntrol of Multihop Wireless N etworks U sing T ransmit Pow er A djustment[C]// Proc. of IEEE INFOCOM’00. [S. l.]: IEEE Press, 2000: 404-413.
[6] Li Xiangyang, Song Wenzhan, Wang Yu. Localized Topology Control for Heterogeneous W ireless Sensor Networks[J]. ACM Transactions on Sensor Networks, 2006, 2(1): 129-153.
[7] Lin Shan, Z hang Jingbin, Zh ou Gang, et al. A TPC: Adaptive Transmission Power Control for Wireless Sensor Networks[C]// Proc. of the 4th International Conference on Embedded Networked Sensor Systems. Ne w York, US A: ACM Press, 2006: 223-236.
[8] Hackmann G, Chipara O, Lu Chenyang. Robust Topology Control for Indoor Wireless Sensor Networks[C]//Proc. of the 6th International Conference on Embedded Networked Sensor Systems. Raleigh, USA: [s. n.], 2008: 57-70.
[9] Moscibroda T, Wattenhofer R, Zollinger A. Topology Control Meets SINR: The Scheduling C omplexity of A rbitrary Topologies[C]//Proc. of the 7th In ternational Symposium on Mobile Ad Hoc Networking and Computing. New York, USA: ACM Press, 2006: 310-321.
[10] Gao Jie, Gu ibas L J, Hershberger J, et al. Ge ometric Spanner for Routing in Mobile Networks[C]//Proc. of the 2nd ACM Symposium on Mobile Ad Hoc Networking and Computing. [S. l.]: ACM Press, 2001: 45-55.
[11] 王出航, 王志軍. 基于路徑損耗的WSN拓?fù)淇刂扑惴╗J].計(jì)算機(jī)工程, 2011, 37(23): 102-104.
[12] Cardieri P. Modeling Interference in Wireless A d Hoc Networks[J]. IE EE Communicat ions Surveys & T utorials, 2010, 12(4): 551-572.
[13] Gao Yan, Ho u J C, Nguyen H. Topology Control for Maintaining Network Connectivity and M aximizing Network Capacity Under the Physical Model[C]//Proc. of the 27th Conference on Computer Communications. [S. l.]: IEEE Press, 2008: 1013-1021.
編輯 顧逸斐
Topology Control Algorithm for WSN Based on Physical Interference Model
LI Yu-min, YU Ji-guo, WAN Sheng-li
(Computer Science College, Qufu Normal University, Rizhao 276826, China)
Topology control is an important issue in Wireless Sensor Network(WSN) research. Most of the existing work on topology control focus on how to reduce energy consumption, but they do not consider the effects of interference. This paper proposes the topology control algorithm PLTCA under physical Signal to Interference plus Noise Ratio(SINR) model, with the objective of maximizing network capacity problem. It constructs topology through computing forward and backward list within three or fewer hops. In PLTCA, power control technology is used and each node can choose their own neighbors by changing the direction of the transmission or the transmission power, so as to control network topology structure. Theoretical analysis sh ows the co nnectivity of the links. This paper proposes a ce ntralized approach, called PLTCA. Simulation results show that the algor ithm can guarantee the network connectivity and decrease the energy dissipation of the network. PLTCA is shown to be superior to the MaxSR algorithm by 10%～20% on the average energy loss of links.
Ad hoc network; Signal to Interference plus Noise Ratio(SINR); Wireless Sensor Network(WSN); topology control; energy loss; connectivity
10.3969/j.issn.1000-3428.2014.05.019
國家自然科學(xué)基金資助項(xiàng)目(11101243)；山東省自然科學(xué)基金資助項(xiàng)目(ZR2012FM023, Z R2012FQ011)；山東省高校科技計(jì)劃基金資助項(xiàng)目(J10LG09, J12LN06)。
李玉民(1988－)，男，碩士研究生，主研方向：無線網(wǎng)絡(luò)；禹繼國，教授、博士；萬勝利，碩士研究生。
2013-04-16
2013-05-17E-mail：liyumin01@126.com
1000-3428(2014)05-0089-05
A
TP301.6
猜你喜歡
無線電波發(fā)射功率防爆要求與檢測(cè)方法工礦自動(dòng)化(2024年6期)2024-08-22 00:00:00 巧用列表來推理小學(xué)生學(xué)習(xí)指導(dǎo)(高年級(jí))(2024年4期)2024-05-07 03:28:46 家紡“全鏈路”升級(jí)紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10 天空地一體化網(wǎng)絡(luò)多中繼鏈路自適應(yīng)調(diào)度技術(shù)移動(dòng)通信(2021年5期)2021-10-25 11:41:48 學(xué)習(xí)運(yùn)用列表法小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2021年4期)2021-04-27 10:14:56 擴(kuò)列吧課堂內(nèi)外(初中版)(2020年5期)2020-06-19 08:11:11 放大轉(zhuǎn)發(fā)中繼器降低發(fā)射功率的選擇策略研究無線互聯(lián)科技(2017年24期)2018-01-22 10:39:24 淺談AC在WLAN系統(tǒng)中的應(yīng)用中國管理信息化(2017年18期)2018-01-04 18:41:52 基于功率分配最優(yōu)中繼選擇的研究物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11 基于3G的VPDN技術(shù)在高速公路備份鏈路中的應(yīng)用中國交通信息化(2014年3期)2014-06-05 03:07:09
李玉民，禹繼國，萬勝利
(曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，山東 日照276826)
基于物理干擾模型的WSN拓?fù)淇刂扑惴?/p>
李玉民，禹繼國，萬勝利
(曲阜師范大學(xué)計(jì)算機(jī)科學(xué)學(xué)院，山東 日照276826)
拓?fù)淇刂剖菬o線傳感器網(wǎng)絡(luò)研究中的重要問題?，F(xiàn)有的大多數(shù)關(guān)于拓?fù)淇刂频墓ぷ骷杏谌绾谓档湍芎?，但是沒有考慮干擾帶來的影響。針對(duì)網(wǎng)絡(luò)容量的最大化問題，提出一種在信號(hào)干擾信噪比模型下的拓?fù)淇刂扑惴≒LTCA。該算法無需任何節(jié)點(diǎn)的位置信息，通過計(jì)算3跳以內(nèi)的前向和后向列表來構(gòu)建拓?fù)?。在PLTCA算法中，采用功率控制技術(shù)，節(jié)點(diǎn)通過改變發(fā)射功率或者發(fā)射方向選擇自己的鄰居節(jié)點(diǎn)，從而控制網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)。通過理論分析對(duì)算法的連通性進(jìn)行論證。仿真結(jié)果表明，PLTCA算法在保證網(wǎng)絡(luò)連通性的基礎(chǔ)上，減少了網(wǎng)絡(luò)總體的能量損耗，與MaxSR算法相比，節(jié)點(diǎn)的平均鏈路能量損耗減少10%～20%。
無線自組網(wǎng)；信號(hào)干擾信噪比；無線傳感器網(wǎng)絡(luò)；拓?fù)淇刂疲荒芰繐p耗；連通性
1 概述
無線傳感器網(wǎng)絡(luò)(Wireless Sensor Net work, WS N)有著廣闊的應(yīng)用前景，它在國家安全、環(huán)境監(jiān)測(cè)、交通管理、空間探索等領(lǐng)域有著重大的應(yīng)用價(jià)值，引起了各界的廣泛關(guān)注。拓?fù)淇刂萍夹g(shù)是無線傳感器網(wǎng)絡(luò)中最重要的技術(shù)之一。在由無線傳感器網(wǎng)絡(luò)生成的網(wǎng)絡(luò)拓?fù)渲校梢灾苯油ㄐ诺?個(gè)節(jié)點(diǎn)之間存在一條拓?fù)溥?。如果沒有拓?fù)淇刂?，所有?jié)點(diǎn)都會(huì)以最大無線傳輸功率工作。網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的無線信號(hào)將覆蓋大量其他節(jié)點(diǎn)，造成無線信號(hào)沖突頻繁，影響節(jié)點(diǎn)的無線通信質(zhì)量，降低網(wǎng)絡(luò)的吞吐率。另一方面，在生成的網(wǎng)絡(luò)拓?fù)渲袑⒋嬖诖罅康倪?，從而?dǎo)致網(wǎng)絡(luò)拓?fù)湫畔⒘看?，路由?jì)算復(fù)雜，浪費(fèi)了寶貴的計(jì)算資源。因此，需要研究無線傳感器網(wǎng)絡(luò)中的拓?fù)淇刂茊栴}，在維持拓?fù)淠承┤中再|(zhì)的前提下，通過調(diào)整節(jié)點(diǎn)的發(fā)送功率來延長網(wǎng)絡(luò)生命周期，提高網(wǎng)絡(luò)吞吐量，降低網(wǎng)絡(luò)干擾，節(jié)約節(jié)點(diǎn)資源。
在無線傳感器網(wǎng)絡(luò)中，如何在消耗最低功率的前提下確定每個(gè)節(jié)點(diǎn)的傳輸功率以維持網(wǎng)絡(luò)連通性，提高空間重用是一個(gè)重要的問題[1]。文獻(xiàn)[2]提出一種拓?fù)淇刂扑惴≧TC。該算法基于RSSI均值計(jì)算節(jié)點(diǎn)間雙向路徑損耗，從而判斷兩節(jié)點(diǎn)間是否存在每跳通信鏈路代價(jià)都小于直接通信鏈路代價(jià)的兩跳路徑，以構(gòu)建局部優(yōu)化拓?fù)洹?/p>
本文提出一種集中式算法，該算法是一種基于物理模型的拓?fù)淇刂扑惴?Path Lo ss Topology C ontrol Al gorithm, PLTCA)。
2 相關(guān)工作
無線傳感器網(wǎng)絡(luò)通常具有大規(guī)模、自組織、隨機(jī)部署、傳感器節(jié)點(diǎn)資源有限、網(wǎng)絡(luò)拓?fù)鋾r(shí)常發(fā)生變化的特點(diǎn)[3]。這些特點(diǎn)反映了拓?fù)淇刂茊栴}的重要性。拓?fù)淇刂频哪繕?biāo)是維持無線自組網(wǎng)的性能(例如，連通性和功率效率)。在現(xiàn)存的拓?fù)淇刂扑惴ㄖ形墨I(xiàn)[4]做了一個(gè)全面的研究。它分為2個(gè)基本的類別：鏈路控制[5]和節(jié)點(diǎn)控制[6]。在鏈路控制中，節(jié)點(diǎn)對(duì)不同的接收器使用不同的發(fā)射功率。相反，在節(jié)點(diǎn)控制中，節(jié)點(diǎn)對(duì)不同的接收器使用相同的發(fā)射功率。節(jié)點(diǎn)控制簡化了鄰居的管理和相關(guān)的MAC控制，鏈路控制會(huì)節(jié)省很多能量。為了在有損耗的無線傳感器網(wǎng)絡(luò)中實(shí)現(xiàn)可靠的拓?fù)?，提出了ATPC算法設(shè)計(jì)，僅僅是為了維持每跳的鏈路質(zhì)量[7]。它不能在多跳網(wǎng)絡(luò)上實(shí)現(xiàn)路徑質(zhì)量的需求，也不能給不同的質(zhì)量標(biāo)準(zhǔn)靈活地配置一個(gè)網(wǎng)絡(luò)。在文獻(xiàn)[8]中，ART協(xié)議是在室內(nèi)環(huán)境中基于鏈路測(cè)量值的拓?fù)淇刂?。在另一方面，?shí)驗(yàn)中的結(jié)果通過采用CTC維持現(xiàn)實(shí)的和真實(shí)的鏈路模型。文獻(xiàn)[9]研究了傳統(tǒng)網(wǎng)絡(luò)模型的局限性，并且在物理模型下分析了拓?fù)淇刂浦墟溌氛{(diào)度的影響。文獻(xiàn)[10]提出局部算法。文獻(xiàn)[11]提出一種面向?qū)嶋H無線環(huán)境應(yīng)用且無需任何位置信息的拓?fù)淇刂扑惴?。本文提出的算法是基于物理干擾模型的拓?fù)淇刂扑惴ā?/p>
3 WSN的干擾模型和網(wǎng)絡(luò)模型
3.1 物理干擾模型
大規(guī)模的路徑損耗被用來描述信號(hào)是如何沿著傳輸路徑變?nèi)醯?。讓gu, v作為節(jié)點(diǎn)vi到節(jié)點(diǎn)vj的通道增益(它通常假設(shè)為恒定的互不依靠的距離)，接收功率表示為：
其中，α是路徑損耗指數(shù)，α的價(jià)值范圍在2～4之間，取決于使用的傳播模型(例α=2是自由空間模型)。一個(gè)傳輸活動(dòng)是否成功取決于2個(gè)因素，也就是接收靈敏度和信號(hào)干擾信噪比(Signal to Interference plus Noise Ratio, SINR)。具體地說，是讓RXmin作為接收器的臨界值來正確地解碼接收信號(hào)，SINR的臨界值為β。一個(gè)信號(hào)可以成功地接收和解碼只要滿足以下2個(gè)公式：
3.2 無線傳感器網(wǎng)絡(luò)模型
在無線傳感器網(wǎng)絡(luò)中假設(shè)每個(gè)節(jié)點(diǎn)u(u∈V)的最大發(fā)射功率pmax。無線傳感器網(wǎng)絡(luò)中的任意節(jié)點(diǎn)u是有向圖G( V, E)的頂點(diǎn)，圖G中的節(jié)點(diǎn)u和v通過一條從u到v的邊連接。如果(u, v)∈E，則(v, u)∈E，G為所有節(jié)點(diǎn)以最大功率發(fā)射生成的初始拓?fù)鋱D。在圖G( V, E)中，pmin(u, v)表示節(jié)點(diǎn)u到達(dá)鄰居節(jié)點(diǎn)v的最小功率，此時(shí)v的接收信號(hào)強(qiáng)度為rssv。用CG(u, v)表示節(jié)點(diǎn)u以功率pmin(u, v)發(fā)射時(shí)的路徑損耗，并將CG(u, v)作為權(quán)值賦給邊(u, v)，其中(u, v)∈E。如果圖G是連通的，則節(jié)點(diǎn)u和v之間必然存在并且至少存在一條鏈路：
則該鏈路的路徑損耗可表示為：
4 算法及其實(shí)現(xiàn)
4.1 無線傳感器拓?fù)淇刂扑惴枋?/p>
相關(guān)定義如下：
(1)pmin(u, v)表示從節(jié)點(diǎn)u到達(dá)節(jié)點(diǎn)v所需的最小發(fā)射功率。
(2)C( u, v)表示路徑損耗。對(duì)于每個(gè)有序節(jié)點(diǎn)對(duì)u和v，定義一個(gè)關(guān)聯(lián)組C( u, v)=(α1, α2)，α1=IDv；α2= pmin(u, v)-rssv。其中，α1是節(jié)點(diǎn)v的編號(hào)；α2表示節(jié)點(diǎn)u以最小功率pmin(u, v)發(fā)射到v的路徑損耗值。如果α2＜α2'或者α2=α2'且α1＜α2'，則(α1, α2)＜(α', α')。
12
(3)forwardlist和backwardlist表示路徑損耗列表，也就是說前向路徑損耗列表和后向路徑損耗列表。forwardlist( u)記錄了節(jié)點(diǎn)u與它的所有鄰居節(jié)點(diǎn)直接通信的關(guān)聯(lián)組C( u, v)=(α1, α2)，u, v∈V，backwardlist( u)記錄了u的所有鄰居節(jié)點(diǎn)與u直接通信的關(guān)聯(lián)組C( u, v)= (α', α')，u, v∈V且v∈N( u)。其中，N( u)表示的是節(jié)
12 點(diǎn)u的鄰居集。假設(shè)每個(gè)節(jié)點(diǎn)u有k個(gè)鄰居節(jié)點(diǎn)，則它具有k個(gè)發(fā)射功率等級(jí)，其最大功率為pmax，最小功率為pmin，第k個(gè)鄰居通信的發(fā)射功率為pk。各節(jié)點(diǎn)依次以計(jì)算好的功率pk廣播包含當(dāng)前發(fā)射功率pk和節(jié)點(diǎn)ID的HELLO報(bào)文，每個(gè)節(jié)點(diǎn)根據(jù)接收的報(bào)文編制前向和后向路徑損耗列表。
算法描述如下：
Step1 節(jié)點(diǎn)u在初始時(shí)以最大功率工作，并廣播探測(cè)拓?fù)涞恼?qǐng)求信息，請(qǐng)求信息中包含節(jié)點(diǎn)的ID、節(jié)點(diǎn)的位置和最大功率等信息。節(jié)點(diǎn)v收到請(qǐng)求信息后，判斷是否大于最小接收功率。根據(jù)SINR物理模型判斷v是否能夠接收u的消息。如果節(jié)點(diǎn)v能收到u的消息，則將v加到N( u)中。
Step2 確定k個(gè)發(fā)射功率，每個(gè)節(jié)點(diǎn)以設(shè)定的最大功率廣播自身的ID號(hào)和位置信息。根據(jù)接收者的消息通過式(1)確定k個(gè)發(fā)送功率。
Step3 列表匯集，各節(jié)點(diǎn)依次以功率pk廣播包含當(dāng)前發(fā)射功率pk和節(jié)點(diǎn)ID的HELLO報(bào)文，每個(gè)節(jié)點(diǎn)根據(jù)接收的報(bào)文編制前向路徑損耗列表和后向路徑損耗列表。
Step4 拓?fù)浣?，每個(gè)節(jié)點(diǎn)以最大發(fā)射功率pmax向它的所有鄰居節(jié)點(diǎn)廣播前向和后向路徑損耗列表，同時(shí)也收集其各個(gè)鄰居節(jié)點(diǎn)的前向和后向路徑損耗列表。計(jì)算節(jié)點(diǎn)u和v之間小于等于3跳的前向和后向路徑，并判斷每一跳的能量消耗是否比節(jié)點(diǎn)u和v直接通信所需能量消耗小。如果u和v之間存在這樣的路徑，則從圖G中移走邊G( u, v)。
4.2 偽代碼
算法主要由4個(gè)階段組成：鄰居生成階段，功率分配階段，列表匯集階段和拓?fù)浣㈦A段。
(1)鄰居生成階段
(2)功率分配階段
假設(shè)每個(gè)節(jié)點(diǎn)u具有k個(gè)功率等級(jí)，其最大功率為pmax，最小功率為pmin，且當(dāng)前級(jí)別功率用pk表示，每個(gè)傳感器節(jié)點(diǎn)的最小接收功率假設(shè)為0.4。
偽代碼如下：
(3)列表匯集階段
各節(jié)點(diǎn)依次以功率pk廣播包含當(dāng)前發(fā)射功率pk和節(jié)點(diǎn)ID的HELLO報(bào)文，每個(gè)節(jié)點(diǎn)根據(jù)接收的報(bào)文編制前向和后向路徑損耗列表。該過程的程序偽代碼如下：
(4)拓?fù)浣㈦A段
每個(gè)節(jié)點(diǎn)以最大發(fā)射功率pmax向它的所有鄰居節(jié)點(diǎn)廣播它的前向路徑損耗列表和后向路徑損耗列表，同時(shí)也收集其各個(gè)鄰居節(jié)點(diǎn)的前向路徑損耗列表和后向路徑損耗列表。從任一節(jié)點(diǎn)u的前向路徑損耗列表中取出第一個(gè)有序?qū)( u, v)，并將C( u, v)從forwardlist( u)中刪除。構(gòu)建一個(gè)節(jié)點(diǎn)v的所有鄰居節(jié)點(diǎn)中滿足C( w, v)＜C( u, v),w∈N( v)的節(jié)點(diǎn)集合Nu(v)。從Nu(v)中任意取出ω，先判斷ω是否為u的鄰居節(jié)點(diǎn)。如果是，則判斷C( u,ω)＜ C( u, v)是否成立，如果成立，則標(biāo)志變量ftPath=True；如果ω不是u的鄰居節(jié)點(diǎn)，判斷是否存在u的鄰居節(jié)點(diǎn)z滿足條件：(C( u, z)∈forwardlist( u))&&(C( z,ω)forwardlist( z) ), z∈N( u)and z≠v 。如果成立，則ftPath= True。同樣，可以判斷是否存在從v到u的3跳或者3跳內(nèi)的后向路徑，并且每一跳的能量消耗都小于直接從v到u的路徑消耗。如果前向和后向存在這樣的路徑，則從圖中刪除邊(u,v)，該過程的程序偽碼如下：
4.3 網(wǎng)絡(luò)連通性分析
定理 如果初始圖G( V, E)連通，則執(zhí)行算法得到的拓?fù)鋱DG'( V',E')也是連通的。
證明：對(duì)于任意2個(gè)節(jié)點(diǎn)u, v∈V，由于圖G( V, E)是連通的，因此圖G( V, E)中節(jié)點(diǎn)u，v之間存在路徑p，設(shè)路徑p為：p={v0=u, v1, v2,…,vn=v}。其中，vi-1和vi( i=0,1,…,n)互為鄰居節(jié)點(diǎn)。假設(shè)節(jié)點(diǎn)之間的通信是滿足雙向性的，僅考慮前向路徑損耗。證明圖G'( V',E')是連通的，只需證明在執(zhí)行完算法后，任意2個(gè)互為鄰居的節(jié)點(diǎn)vi-1和vi( i=0,1,…,n)之間是存在通信鏈路的。執(zhí)行算法后，G'( V',E')中每個(gè)節(jié)點(diǎn)v都建立起了自己的前向路徑損耗列表forwardlist(vi)并且收集了鄰居節(jié)點(diǎn)的后向路徑損耗列表backwardlist(vi+1)，如果2個(gè)節(jié)點(diǎn)是鄰居，則前向路徑損耗列表forwardlist(vi)中一定存在C( vi, vi+1)。因此，只需證明vi和vi+1之間存在通信鏈路。假設(shè)執(zhí)行算法后vi和vi+1之間不存在通信鏈路，則邊e( vi, vi+1)一定不存在。根據(jù)算法的執(zhí)行規(guī)則，在節(jié)點(diǎn)vi+1的后向路徑損耗列表backwardlist(vi+1)中存在C(ω,vi +1)，在集合Nv(vi+1)中一定存在滿足C(ω,vi +1)＜C( vi, vi+1)的節(jié)點(diǎn)ω。那么分為以下2種情況：
(1)節(jié)點(diǎn)vi的前向路徑損耗列表forwardlist(vi)中有C( vi,ω)＜C( vi, vi +1)，ω為vi和vi+1的鄰居，且在vi和vi+1之間存在C( v,ω)＜C(ω,vi+1)，也就是說節(jié)點(diǎn)vi和節(jié)點(diǎn)vi+1之間存在通信鏈路vi→ω→vi+1。
(2)在節(jié)點(diǎn)vi的前向路徑損耗列表forwardlist(vi)中存在C( vi, z), z∈N( vi)，在z的前向路徑損耗列表forwardlist(z)中存在C( z,ω)，且滿足max(C( u, z), C( z,ω))＜C( vi, vi +1)，可見在vi和vi+1之間存在C( vi, z)＜C( z,ω)＜C( z, vi +1)，即vi和vi+1之間存在通信路徑vi→z→ω→vi+1。因此，vi和vi+1之間存在通信鏈路，與前邊的假設(shè)是相互矛盾的。所以如果初始圖G( V, E)連通，則執(zhí)行算法得到的拓?fù)鋱DG'( V',E')也是連通的。
5 仿真結(jié)果分析
PLTCA采用路徑損耗構(gòu)建網(wǎng)絡(luò)拓?fù)?，且無需節(jié)點(diǎn)的位置信息。運(yùn)用Java仿真器對(duì)PLTCA算法與MaxSR算法進(jìn)行了對(duì)比仿真。
在實(shí)驗(yàn)中，路徑損耗指數(shù)α在整個(gè)網(wǎng)絡(luò)中是相同的，取α=2。節(jié)點(diǎn)的發(fā)射功率是通過路徑損耗模型計(jì)算的，基于這種參數(shù)配置，提出了以下仿真：
方案1 將50個(gè)節(jié)點(diǎn)隨機(jī)布置在500×400的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)賦予唯一的ID號(hào)。執(zhí)行PLTCA算法得到的拓?fù)浣Y(jié)構(gòu)與執(zhí)行MaxSR[13]算法得到的拓?fù)浣Y(jié)構(gòu)進(jìn)行了對(duì)比，如圖1和圖2所示。其中，MaxSR算法執(zhí)行后鏈路數(shù)為52，執(zhí)行PLTCA算法后鏈路數(shù)為49。
圖1 P LTCA算法的執(zhí)行結(jié)果1
圖2 MaxSR算法的執(zhí)行結(jié)果1
方案2 將80個(gè)節(jié)點(diǎn)隨機(jī)布置在500×400的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)賦予唯一的ID號(hào)。執(zhí)行PLTCA算法得到的拓?fù)浣Y(jié)構(gòu)與執(zhí)行算法MaxSR的拓?fù)浣Y(jié)構(gòu)進(jìn)行對(duì)比，如圖3和圖4所示。其中，MaxSR算法執(zhí)行后鏈路數(shù)為93，執(zhí)行PLTCA算法后鏈路數(shù)為82。
圖3 P LTCA算法的執(zhí)行結(jié)果2
圖4 MaxSR算法的執(zhí)行結(jié)果2
方案3 將110個(gè)節(jié)點(diǎn)隨機(jī)布置在500×400的區(qū)域內(nèi)，每個(gè)節(jié)點(diǎn)賦予唯一的ID號(hào)。執(zhí)行PLTCA算法得到的拓?fù)浣Y(jié)構(gòu)與執(zhí)行算法MaxSR的拓?fù)浣Y(jié)構(gòu)進(jìn)行了對(duì)比，如圖5和圖6所示。其中，MaxSR算法執(zhí)行后鏈路數(shù)為132，執(zhí)行PLTCA算法后鏈路數(shù)為121。
圖5 L TCA算法的執(zhí)行結(jié)果3
圖6 MaxSR算法的執(zhí)行結(jié)果3
圖7、圖8為在相同的傳感器節(jié)點(diǎn)部署條件下，分別對(duì)激活鏈路數(shù)和平均鏈路路經(jīng)損耗進(jìn)行了對(duì)比，其中，激活的鏈路指的是拓?fù)鋱D中的鏈路數(shù)，平均鏈路路經(jīng)損耗指的是所有鏈路路經(jīng)損耗的和除以鏈路數(shù)。
圖7 激活鏈路數(shù)對(duì)比
圖8 平均鏈路路徑損耗對(duì)比
通過以上仿真實(shí)驗(yàn)，對(duì)2個(gè)算法的性能結(jié)果進(jìn)行了比較。結(jié)果表明，算法PLTCA的性能較為優(yōu)越，算法PLTCA在節(jié)點(diǎn)的平均鏈路路徑損耗上優(yōu)于MaxSR算法10%～20%。物理模型下研究拓?fù)淇刂聘咏鎸?shí)情況。
6 結(jié)束語
實(shí)際的無線環(huán)境中具有多種不規(guī)則和多徑傳播現(xiàn)象，如果沒有拓?fù)淇刂扑惴?，無線傳感器網(wǎng)絡(luò)節(jié)點(diǎn)將被迫使用大發(fā)射功率發(fā)送信息以確保通信和網(wǎng)絡(luò)連通。本文提出的算法并不需要任何基于位置的信息，適用于實(shí)際無線環(huán)境下的普通節(jié)點(diǎn)、異構(gòu)網(wǎng)絡(luò)，減少了網(wǎng)絡(luò)總體能量消耗，延長了網(wǎng)絡(luò)生命周期。仿真結(jié)果表明，PLTCA算法具有較好的性能。在下一步的工作中，將進(jìn)一步降低計(jì)算復(fù)雜度以及通信開銷。
[1] Hu L. A Novel Topology Control for Multihop Pac ket Radio Networks[C]//Proc. of IE EE INF OCOM’91. Mia mi, US A: [s. n.], 1991: 1084-1093.
[2] 王出航. 基于RSSI均值的無線傳感器網(wǎng)絡(luò)拓?fù)淇刂扑惴╗J].計(jì)算機(jī)應(yīng)用, 2012, 32(2): 352-354, 358.
[3] Akyildiz I F, Su W eilian, Sankarasubramaniam Y, et al. A Survey on Sensor Networks[J]. IEEE Communications Magazine, 2002, 40(8): 102-114.
[4] Simon G. Probabilistic Wireless Network Simulator[EB/OL]. (2008-06-23). http://www.isis.vanderbilt.edu/projects/nest/prowler.
[5] Ramanathan R, Hain R. Topology Co ntrol of Multihop Wireless N etworks U sing T ransmit Pow er A djustment[C]// Proc. of IEEE INFOCOM’00. [S. l.]: IEEE Press, 2000: 404-413.
[6] Li Xiangyang, Song Wenzhan, Wang Yu. Localized Topology Control for Heterogeneous W ireless Sensor Networks[J]. ACM Transactions on Sensor Networks, 2006, 2(1): 129-153.
[7] Lin Shan, Z hang Jingbin, Zh ou Gang, et al. A TPC: Adaptive Transmission Power Control for Wireless Sensor Networks[C]// Proc. of the 4th International Conference on Embedded Networked Sensor Systems. Ne w York, US A: ACM Press, 2006: 223-236.
[8] Hackmann G, Chipara O, Lu Chenyang. Robust Topology Control for Indoor Wireless Sensor Networks[C]//Proc. of the 6th International Conference on Embedded Networked Sensor Systems. Raleigh, USA: [s. n.], 2008: 57-70.
[9] Moscibroda T, Wattenhofer R, Zollinger A. Topology Control Meets SINR: The Scheduling C omplexity of A rbitrary Topologies[C]//Proc. of the 7th In ternational Symposium on Mobile Ad Hoc Networking and Computing. New York, USA: ACM Press, 2006: 310-321.
[10] Gao Jie, Gu ibas L J, Hershberger J, et al. Ge ometric Spanner for Routing in Mobile Networks[C]//Proc. of the 2nd ACM Symposium on Mobile Ad Hoc Networking and Computing. [S. l.]: ACM Press, 2001: 45-55.
[11] 王出航, 王志軍. 基于路徑損耗的WSN拓?fù)淇刂扑惴╗J].計(jì)算機(jī)工程, 2011, 37(23): 102-104.
[12] Cardieri P. Modeling Interference in Wireless A d Hoc Networks[J]. IE EE Communicat ions Surveys & T utorials, 2010, 12(4): 551-572.
[13] Gao Yan, Ho u J C, Nguyen H. Topology Control for Maintaining Network Connectivity and M aximizing Network Capacity Under the Physical Model[C]//Proc. of the 27th Conference on Computer Communications. [S. l.]: IEEE Press, 2008: 1013-1021.
編輯 顧逸斐
Topology Control Algorithm for WSN Based on Physical Interference Model
LI Yu-min, YU Ji-guo, WAN Sheng-li
(Computer Science College, Qufu Normal University, Rizhao 276826, China)
Topology control is an important issue in Wireless Sensor Network(WSN) research. Most of the existing work on topology control focus on how to reduce energy consumption, but they do not consider the effects of interference. This paper proposes the topology control algorithm PLTCA under physical Signal to Interference plus Noise Ratio(SINR) model, with the objective of maximizing network capacity problem. It constructs topology through computing forward and backward list within three or fewer hops. In PLTCA, power control technology is used and each node can choose their own neighbors by changing the direction of the transmission or the transmission power, so as to control network topology structure. Theoretical analysis sh ows the co nnectivity of the links. This paper proposes a ce ntralized approach, called PLTCA. Simulation results show that the algor ithm can guarantee the network connectivity and decrease the energy dissipation of the network. PLTCA is shown to be superior to the MaxSR algorithm by 10%～20% on the average energy loss of links.
Ad hoc network; Signal to Interference plus Noise Ratio(SINR); Wireless Sensor Network(WSN); topology control; energy loss; connectivity
10.3969/j.issn.1000-3428.2014.05.019
國家自然科學(xué)基金資助項(xiàng)目(11101243)；山東省自然科學(xué)基金資助項(xiàng)目(ZR2012FM023, Z R2012FQ011)；山東省高校科技計(jì)劃基金資助項(xiàng)目(J10LG09, J12LN06)。
李玉民(1988－)，男，碩士研究生，主研方向：無線網(wǎng)絡(luò)；禹繼國，教授、博士；萬勝利，碩士研究生。
2013-04-16
2013-05-17E-mail：liyumin01@126.com
1000-3428(2014)05-0089-05
A
TP301.6
猜你喜歡
工礦自動(dòng)化(2024年6期)2024-08-22 00:00:00
小學(xué)生學(xué)習(xí)指導(dǎo)(高年級(jí))(2024年4期)2024-05-07 03:28:46
紡織科學(xué)研究(2023年9期)2023-10-23 11:18:10
移動(dòng)通信(2021年5期)2021-10-25 11:41:48
小學(xué)生學(xué)習(xí)指導(dǎo)(中年級(jí))(2021年4期)2021-04-27 10:14:56
課堂內(nèi)外(初中版)(2020年5期)2020-06-19 08:11:11
無線互聯(lián)科技(2017年24期)2018-01-22 10:39:24
中國管理信息化(2017年18期)2018-01-04 18:41:52
物聯(lián)網(wǎng)技術(shù)(2017年2期)2017-03-15 17:18:11
中國交通信息化(2014年3期)2014-06-05 03:07:09
