基于物理干擾模型的WSN拓撲控制算法

李玉民，禹繼國，萬勝利

(曲阜師范大學計算機科學學院，山東 日照276826)

基于物理干擾模型的WSN拓撲控制算法

李玉民，禹繼國，萬勝利

(曲阜師范大學計算機科學學院，山東 日照276826)

拓撲控制是無線傳感器網絡研究中的重要問題。現有的大多數關于拓撲控制的工作集中于如何降低能耗，但是沒有考慮干擾帶來的影響。針對網絡容量的最大化問題，提出一種在信號干擾信噪比模型下的拓撲控制算法PLTCA。該算法無需任何節點的位置信息，通過計算3跳以內的前向和后向列表來構建拓撲。在PLTCA算法中，采用功率控制技術，節點通過改變發射功率或者發射方向選擇自己的鄰居節點，從而控制網絡拓撲結構。通過理論分析對算法的連通性進行論證。仿真結果表明，PLTCA算法在保證網絡連通性的基礎上，減少了網絡總體的能量損耗，與MaxSR算法相比，節點的平均鏈路能量損耗減少10%～20%。

無線自組網；信號干擾信噪比；無線傳感器網絡；拓撲控制；能量損耗；連通性

1 概述

無線傳感器網絡(Wireless Sensor Net work, WS N)有著廣闊的應用前景，它在國家安全、環境監測、交通管理、空間探索等領域有著重大的應用價值，引起了各界的廣泛關注。拓撲控制技術是無線傳感器網絡中最重要的技術之一。在由無線傳感器網絡生成的網絡拓撲中，可以直接通信的2個節點之間存在一條拓撲邊。如果沒有拓撲控制，所有節點都會以最大無線傳輸功率工作。網絡中每個節點的無線信號將覆蓋大量其他節點，造成無線信號沖突頻繁，影響節點的無線通信質量，降低網絡的吞吐率。另一方面，在生成的網絡拓撲中將存在大量的邊，從而導致網絡拓撲信息量大，路由計算復雜，浪費了寶貴的計算資源。因此，需要研究無線傳感器網絡中的拓撲控制問題，在維持拓撲某些全局性質的前提下，通過調整節點的發送功率來延長網絡生命周期，提高網絡吞吐量，降低網絡干擾，節約節點資源。

在無線傳感器網絡中，如何在消耗最低功率的前提下確定每個節點的傳輸功率以維持網絡連通性，提高空間重用是一個重要的問題[1]。文獻[2]提出一種拓撲控制算法RTC。該算法基于RSSI均值計算節點間雙向路徑損耗，從而判斷兩節點間是否存在每跳通信鏈路代價都小于直接通信鏈路代價的兩跳路徑，以構建局部優化拓撲。

本文提出一種集中式算法，該算法是一種基于物理模型的拓撲控制算法(Path Lo ss Topology C ontrol Al gorithm, PLTCA)。

2 相關工作

無線傳感器網絡通常具有大規模、自組織、隨機部署、傳感器節點資源有限、網絡拓撲時常發生變化的特點[3]。這些特點反映了拓撲控制問題的重要性。拓撲控制的目標是維持無線自組網的性能(例如，連通性和功率效率)。在現存的拓撲控制算法中文獻[4]做了一個全面的研究。它分為2個基本的類別：鏈路控制[5]和節點控制[6]。在鏈路控制中，節點對不同的接收器使用不同的發射功率。相反，在節點控制中，節點對不同的接收器使用相同的發射功率。節點控制簡化了鄰居的管理和相關的MAC控制，鏈路控制會節省很多能量。為了在有損耗的無線傳感器網絡中實現可靠的拓撲，提出了ATPC算法設計，僅僅是為了維持每跳的鏈路質量[7]。它不能在多跳網絡上實現路徑質量的需求，也不能給不同的質量標準靈活地配置一個網絡。在文獻[8]中，ART協議是在室內環境中基于鏈路測量值的拓撲控制。在另一方面，實驗中的結果通過采用CTC維持現實的和真實的鏈路模型。文獻[9]研究了傳統網絡模型的局限性，并且在物理模型下分析了拓撲控制中鏈路調度的影響。文獻[10]提出局部算法。文獻[11]提出一種面向實際無線環境應用且無需任何位置信息的拓撲控制算法。本文提出的算法是基于物理干擾模型的拓撲控制算法。

3 WSN的干擾模型和網絡模型

3.1 物理干擾模型

大規模的路徑損耗被用來描述信號是如何沿著傳輸路徑變弱的。讓gu, v作為節點vi到節點vj的通道增益(它通常假設為恒定的互不依靠的距離)，接收功率表示為：

其中，α是路徑損耗指數，α的價值范圍在2～4之間，取決于使用的傳播模型(例α=2是自由空間模型)。一個傳輸活動是否成功取決于2個因素，也就是接收靈敏度和信號干擾信噪比(Signal to Interference plus Noise Ratio, SINR)。具體地說，是讓RXmin作為接收器的臨界值來正確地解碼接收信號，SINR的臨界值為β。一個信號可以成功地接收和解碼只要滿足以下2個公式：

3.2 無線傳感器網絡模型

在無線傳感器網絡中假設每個節點u(u∈V)的最大發射功率pmax。無線傳感器網絡中的任意節點u是有向圖G( V, E)的頂點，圖G中的節點u和v通過一條從u到v的邊連接。如果(u, v)∈E，則(v, u)∈E，G為所有節點以最大功率發射生成的初始拓撲圖。在圖G( V, E)中，pmin(u, v)表示節點u到達鄰居節點v的最小功率，此時v的接收信號強度為rssv。用CG(u, v)表示節點u以功率pmin(u, v)發射時的路徑損耗，并將CG(u, v)作為權值賦給邊(u, v)，其中(u, v)∈E。如果圖G是連通的，則節點u和v之間必然存在并且至少存在一條鏈路：

則該鏈路的路徑損耗可表示為：

4 算法及其實現

4.1 無線傳感器拓撲控制算法描述

相關定義如下：

(1)pmin(u, v)表示從節點u到達節點v所需的最小發射功率。

(2)C( u, v)表示路徑損耗。對于每個有序節點對u和v，定義一個關聯組C( u, v)=(α1, α2)，α1=IDv；α2= pmin(u, v)-rssv。其中，α1是節點v的編號；α2表示節點u以最小功率pmin(u, v)發射到v的路徑損耗值。如果α2＜α2'或者α2=α2'且α1＜α2'，則(α1, α2)＜(α', α')。

12

(3)forwardlist和backwardlist表示路徑損耗列表，也就是說前向路徑損耗列表和后向路徑損耗列表。forwardlist( u)記錄了節點u與它的所有鄰居節點直接通信的關聯組C( u, v)=(α1, α2)，u, v∈V，backwardlist( u)記錄了u的所有鄰居節點與u直接通信的關聯組C( u, v)= (α', α')，u, v∈V且v∈N( u)。其中，N( u)表示的是節

12 點u的鄰居集。假設每個節點u有k個鄰居節點，則它具有k個發射功率等級，其最大功率為pmax，最小功率為pmin，第k個鄰居通信的發射功率為pk。各節點依次以計算好的功率pk廣播包含當前發射功率pk和節點ID的HELLO報文，每個節點根據接收的報文編制前向和后向路徑損耗列表。

算法描述如下：

Step1 節點u在初始時以最大功率工作，并廣播探測拓撲的請求信息，請求信息中包含節點的ID、節點的位置和最大功率等信息。節點v收到請求信息后，判斷是否大于最小接收功率。根據SINR物理模型判斷v是否能夠接收u的消息。如果節點v能收到u的消息，則將v加到N( u)中。

Step2 確定k個發射功率，每個節點以設定的最大功率廣播自身的ID號和位置信息。根據接收者的消息通過式(1)確定k個發送功率。

Step3 列表匯集，各節點依次以功率pk廣播包含當前發射功率pk和節點ID的HELLO報文，每個節點根據接收的報文編制前向路徑損耗列表和后向路徑損耗列表。

Step4 拓撲建立，每個節點以最大發射功率pmax向它的所有鄰居節點廣播前向和后向路徑損耗列表，同時也收集其各個鄰居節點的前向和后向路徑損耗列表。計算節點u和v之間小于等于3跳的前向和后向路徑，并判斷每一跳的能量消耗是否比節點u和v直接通信所需能量消耗小。如果u和v之間存在這樣的路徑，則從圖G中移走邊G( u, v)。

4.2 偽代碼

算法主要由4個階段組成：鄰居生成階段，功率分配階段，列表匯集階段和拓撲建立階段。

(1)鄰居生成階段

(2)功率分配階段

假設每個節點u具有k個功率等級，其最大功率為pmax，最小功率為pmin，且當前級別功率用pk表示，每個傳感器節點的最小接收功率假設為0.4。

偽代碼如下：

(3)列表匯集階段

各節點依次以功率pk廣播包含當前發射功率pk和節點ID的HELLO報文，每個節點根據接收的報文編制前向和后向路徑損耗列表。該過程的程序偽代碼如下：

(4)拓撲建立階段

每個節點以最大發射功率pmax向它的所有鄰居節點廣播它的前向路徑損耗列表和后向路徑損耗列表，同時也收集其各個鄰居節點的前向路徑損耗列表和后向路徑損耗列表。從任一節點u的前向路徑損耗列表中取出第一個有序對C( u, v)，并將C( u, v)從forwardlist( u)中刪除。構建一個節點v的所有鄰居節點中滿足C( w, v)＜C( u, v),w∈N( v)的節點集合Nu(v)。從Nu(v)中任意取出ω，先判斷ω是否為u的鄰居節點。如果是，則判斷C( u,ω)＜ C( u, v)是否成立，如果成立，則標志變量ftPath=True；如果ω不是u的鄰居節點，判斷是否存在u的鄰居節點z滿足條件：(C( u, z)∈forwardlist( u))&&(C( z,ω)forwardlist( z) ), z∈N( u)and z≠v 。如果成立，則ftPath= True。同樣，可以判斷是否存在從v到u的3跳或者3跳內的后向路徑，并且每一跳的能量消耗都小于直接從v到u的路徑消耗。如果前向和后向存在這樣的路徑，則從圖中刪除邊(u,v)，該過程的程序偽碼如下：

4.3 網絡連通性分析

定理 如果初始圖G( V, E)連通，則執行算法得到的拓撲圖G'( V',E')也是連通的。

證明：對于任意2個節點u, v∈V，由于圖G( V, E)是連通的，因此圖G( V, E)中節點u，v之間存在路徑p，設路徑p為：p={v0=u, v1, v2,…,vn=v}。其中，vi-1和vi( i=0,1,…,n)互為鄰居節點。假設節點之間的通信是滿足雙向性的，僅考慮前向路徑損耗。證明圖G'( V',E')是連通的，只需證明在執行完算法后，任意2個互為鄰居的節點vi-1和vi( i=0,1,…,n)之間是存在通信鏈路的。執行算法后，G'( V',E')中每個節點v都建立起了自己的前向路徑損耗列表forwardlist(vi)并且收集了鄰居節點的后向路徑損耗列表backwardlist(vi+1)，如果2個節點是鄰居，則前向路徑損耗列表forwardlist(vi)中一定存在C( vi, vi+1)。因此，只需證明vi和vi+1之間存在通信鏈路。假設執行算法后vi和vi+1之間不存在通信鏈路，則邊e( vi, vi+1)一定不存在。根據算法的執行規則，在節點vi+1的后向路徑損耗列表backwardlist(vi+1)中存在C(ω,vi +1)，在集合Nv(vi+1)中一定存在滿足C(ω,vi +1)＜C( vi, vi+1)的節點ω。那么分為以下2種情況：

(1)節點vi的前向路徑損耗列表forwardlist(vi)中有C( vi,ω)＜C( vi, vi +1)，ω為vi和vi+1的鄰居，且在vi和vi+1之間存在C( v,ω)＜C(ω,vi+1)，也就是說節點vi和節點vi+1之間存在通信鏈路vi→ω→vi+1。

(2)在節點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之間存在通信鏈路，與前邊的假設是相互矛盾的。所以如果初始圖G( V, E)連通，則執行算法得到的拓撲圖G'( V',E')也是連通的。

5 仿真結果分析

PLTCA采用路徑損耗構建網絡拓撲，且無需節點的位置信息。運用Java仿真器對PLTCA算法與MaxSR算法進行了對比仿真。

在實驗中，路徑損耗指數α在整個網絡中是相同的，取α=2。節點的發射功率是通過路徑損耗模型計算的，基于這種參數配置，提出了以下仿真：

方案1 將50個節點隨機布置在500×400的區域內，每個節點賦予唯一的ID號。執行PLTCA算法得到的拓撲結構與執行MaxSR[13]算法得到的拓撲結構進行了對比，如圖1和圖2所示。其中，MaxSR算法執行后鏈路數為52，執行PLTCA算法后鏈路數為49。

圖1 P LTCA算法的執行結果1

圖2 MaxSR算法的執行結果1

方案2 將80個節點隨機布置在500×400的區域內，每個節點賦予唯一的ID號。執行PLTCA算法得到的拓撲結構與執行算法MaxSR的拓撲結構進行對比，如圖3和圖4所示。其中，MaxSR算法執行后鏈路數為93，執行PLTCA算法后鏈路數為82。

圖3 P LTCA算法的執行結果2

圖4 MaxSR算法的執行結果2

方案3 將110個節點隨機布置在500×400的區域內，每個節點賦予唯一的ID號。執行PLTCA算法得到的拓撲結構與執行算法MaxSR的拓撲結構進行了對比，如圖5和圖6所示。其中，MaxSR算法執行后鏈路數為132，執行PLTCA算法后鏈路數為121。

圖5 L TCA算法的執行結果3

圖6 MaxSR算法的執行結果3

圖7、圖8為在相同的傳感器節點部署條件下，分別對激活鏈路數和平均鏈路路經損耗進行了對比，其中，激活的鏈路指的是拓撲圖中的鏈路數，平均鏈路路經損耗指的是所有鏈路路經損耗的和除以鏈路數。

圖7 激活鏈路數對比

圖8 平均鏈路路徑損耗對比

通過以上仿真實驗，對2個算法的性能結果進行了比較。結果表明，算法PLTCA的性能較為優越，算法PLTCA在節點的平均鏈路路徑損耗上優于MaxSR算法10%～20%。物理模型下研究拓撲控制更接近真實情況。

6 結束語

實際的無線環境中具有多種不規則和多徑傳播現象，如果沒有拓撲控制算法，無線傳感器網絡節點將被迫使用大發射功率發送信息以確保通信和網絡連通。本文提出的算法并不需要任何基于位置的信息，適用于實際無線環境下的普通節點、異構網絡，減少了網絡總體能量消耗，延長了網絡生命周期。仿真結果表明，PLTCA算法具有較好的性能。在下一步的工作中，將進一步降低計算復雜度以及通信開銷。

[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均值的無線傳感器網絡拓撲控制算法[J].計算機應用, 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拓撲控制算法[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

國家自然科學基金資助項目(11101243)；山東省自然科學基金資助項目(ZR2012FM023, Z R2012FQ011)；山東省高校科技計劃基金資助項目(J10LG09, J12LN06)。

李玉民(1988－)，男，碩士研究生，主研方向：無線網絡；禹繼國，教授、博士；萬勝利，碩士研究生。

2013-04-16

2013-05-17E-mail：liyumin01@126.com

1000-3428(2014)05-0089-05

A

TP301.6