無線傳感器網絡中雙層受限中繼節點放置算法研究

向浩凱 周小平 王家南 李莉 黃佳慧

摘要： 針對在三維空間中，對于中繼節點（RN）的位置受限并且是雙層拓撲的情況，提出了一種基于混合整數線性規劃的中繼節點放置算法，該算法首先考慮三維空間中繼節點放置的物理層模型，然后基于混合整數線性規劃（MIPS）給出最優能效的分簇，使得每個傳感器節點與相應簇頭之間的傳輸距離最小.仿真結果表明：與只考慮最小化簇內距離的中繼節點放置算法相比，本算法在降低重傳率和延長網絡生命周期方面都有較大的改善.

關鍵詞：

中繼節點； 無線傳感器網絡； 雙層受限； 整數線性規劃

中圖分類號： TN 929.5文獻標志碼： A文章編號： 10005137（2018）02022005

Research on the placement algorithm of twotiered constrained

relay nodes in wireless sensor networks

Xiang Haokai， Zhou Xiaoping*， Wang Jianan， Li Li， Huang Jiahui

（The College of Information，Mechanical and Electrical Engineering，Shanghai Normal University，Shanghai 200234，China）

Abstract：

In threedimensional space，when the location of relay nodes is limited and it is a twolayer topology，a relay location algorithm based on mixed integer linear programming （MILP） is proposed.The algorithm first considers the physical layer model placed by relay nodes in threedimensional space.Then，the optimal energy efficient clustering is given based on mixed integer linear programming.So that the transmission distance between each sensor node and its corresponding cluster head is the minimized.The simulation results show that compared with the traditional relay node algorithm that only considers the minimum intra cluster distance，the algorithm has a great improvement in reducing the retransmission rate and prolonging the life cycle of the network.

Key words：

relay node； wireless sensor networks； twotiered constrained； mixed integer linear programming

收稿日期： 20171227

基金項目： 上海市自然科學基金項目（16ZR1424500）

作者簡介： 向浩凱（1993-），男，碩士研究生，主要從事無線傳感器網絡方面的研究.Email：2283557476@qq.com

導師簡介： 周小平（1981-），男，博士，副教授，主要從事寬帶無線通信、新一代移動通信和物聯網技術方面的研究.Email：zxpshnu@163.com

*通信作者

引用格式： 向浩凱，周小平，王家南，等.無線傳感器網絡中雙層受限中繼節點放置算法研究 [J].上海師范大學學報（自然科學版），2018，47（2）：220-224.

Citation format： Xiang H K，Zhou X P，Wang J N，et al.Research on the placement algorithm of twotiered constrained relay nodes in Wireless Sensor Networks [J].Journal of Shanghai Normal University （Natural Sciences），2018，47（2）：220-224.

0引言

網絡節點的合理布局是無線傳感器（WSN）網絡運行的首要前提.在WSN的大多數應用場景中，傳感器節點（SN）和網關節點（GN）的布局位置相對固定，并且它們的能量往往難以補充，為了延長網絡生命周期，提升網絡連通性與可靠性，可以通過放置中繼節點（RN）的方式來實現[1].因此，中繼節點布局的優劣往往決定了無線傳感器網絡的生命周期、通信質量[2].

RN的布局分為單層網絡結構（singletiered）和雙層網絡結構（twotiered）兩種[3].在單層網絡結構中，SN和RN都需要轉發數據，而在雙層網絡結構中，SN只需要將自身采集的數據傳送給RN，不需要轉發其他傳感器節點的數據.文獻[4]對于單層網絡結構的情況，將最少放置RN的問題轉化成一個Steiner樹的問題，解出最小化的Steiner點數和邊長，便可得到最小放置RN的個數和位置.文獻[5]對于文獻[4]中的RN放置位置不受限的問題進行改進，中繼節點只能放置在預先設定的位置上，給出了基于多項式時間復雜度的近似算法.

文獻[6]提出了一步受限RN放置算法，保證SN與基站相連接的情況下放置最小數量的中繼節點.針對文獻[6]沒有考慮網絡的容錯性能，文獻[7]和[8]在滿足網絡容錯需求的情況下，基于Steiner樹的理論給出最小數量放置RN的探索式算法.

上述文獻主要基于簇內距離最小化來實現RN的最優化放置，沒有將物理因素的影響考慮在內.本文作者考慮在三維空間中，物理層參數（信道衰落和信噪比）對RN放置的影響，給出基于瑞利衰落的現實物理層模型；同時，基于混合整數線性規劃（MIPS），得到SN與其簇頭之間傳輸距離的最小值，從而在滿足通信要求的前提下，得到RN的最優化放置位置.

1系統模型

本研究場景的系統模型如圖1所示，其中RN作為簇頭，負責收集來自SN的數據并將其轉發到基站，對于此問題，需要找到最優化的RN部署方案，使每一個傳感器都與基站連接.

基站與基站之間是通過有線的方式連接的，u代表發射節點，v代表接收節點，發射功率分別為Pu和Pv，兩個節點之間的信道增益為au，v，瑞利塊衰落在同一個塊中信道增益保持常量.在本系統中，考慮了其他節點對節點v的干擾，節點w對節點v的衰減系數為aw，v，服從瑞利分布.從節點v所獲得的接收信號

2雙層受限RN放置算法

為了能夠最優化放置RN，減少所提方案的復雜度，假設節點u的發射范圍為ρu，它的大小由節點發射功率決定，也就是說當節點v與節點u之間的距離不超過ρu，那么節點u就能把節點v選作為父節點.

由（4），（5）式可知，節點v的平均接收信噪比

其中Cw，v=∏z≠u，v，wz∈Nγ—w，vγ—w，v-γ—z，v，Y表示隨機事件，y表示隨機事件中的一個具體事例，N表示發射節點的集合.

為了提升WSN在運行過程中的通信質量，減小節點的死亡速度，目標是將SN分配到最接近的RN，使成員節點的能量消耗最小.在滿足通信要求的情況下，部署最少數量的RNs以覆蓋所有的傳感區域是首要目標.為了得到RN的最優化放置位置，考慮了通信質量、網絡覆蓋范圍和信號接收概率.通過將SN分配到最接近的RN，最大限度提高WSN的壽命，解決集群形成的問題，最終將問題轉化成簇內通信距離最小化的問題.

WSN能量的消耗將會隨成員節點與其對應RN距離的增加而增大.其距離

其中（xu，yu，hu），（Xv，Yv，Hv）是節點su和中繼節點RNv的坐標.

假設傳感范圍是面積為B的正方形區域，則節點u的最大通信半徑為ρu，可以覆蓋的區域面積為πρ2u.

令αuv為每個傳感器節點分配給相應簇頭的判斷因子，它是一個布爾型變量，當節點su所對應的簇頭是RNv時，αuv=1；否則αuv=0.

在確保通信質量的情況下，使網絡的數據傳輸距離最小.即求

其中限制條件（13）～（16）式分別保證了每個SN可以分配給一個RN，每個SN必須在一個RN的傳輸范圍ρu內，每一次的發射信號能被成功接收以及決定系數αuv為布爾型.

3結果仿真與分析

為驗證本算法相對于不考慮物理層因素的傳統中繼放置算法的優越性，對算法的性能進行仿真.仿真實驗的區域面積為100 m×100 m，SN的個數為80，RN預先設定的放置位置個數為5，SN采用均勻部署方式.圖2給出了一步受限RN放置（OSRP）算法[6]和本算法在SN在傳包效率上的仿真，圖3比較了OSRP算法和本算法在傳感網生命周期方面的性能.

由圖2可以看出，本算法相對于OSRP算法減少了SN的重傳次數，使傳包效率得到提升.從圖3 SN數隨時間的變化曲線可以看出4 h之后，相對于OSRP算法，本算法有效地減少了SNs的死亡個數，延長了網絡生命周期.

4結論

針對在雙層受限結構的WSN中，傳統的RN放置算法會導致丟包率高和網絡生命周期短的問題，本文作者提出了基于MIPS的RN放置算法.該算法考慮了RN放置的物理層因素，改善了網絡通信質量，提升了傳包效率，延長了WSN的生命周期.因此對于雙層受限結構的WSN來說，本算法是一種較好的RN放置方案.

參考文獻：

[1]Tripathi A，Gupta P，Trivedi A，et al.Wireless sensor node placement using hybrid genetic programming and genetic algorithms [J].International Journal of Intelligent Information Technologies，2011，7（2）：63-83.

[2]Bari A，Jaekel A，Jiang J，et al.Design of fault tolerant wireless sensor networks satisfying survivability and lifetime requirements [J].Computer Communications，2012，35（3）：320-333.

[3]Iqbal Z，Kim K，Lee H N.A cooperative wireless sensor network for indoor industrial monitoring [J].IEEE Transactions on Industrial Informatics，2017，13（2）：482-491.

[4]Cheng X Z，Du D Z，Wang L S，et al.Relay sensor placement in wireless sensor networks [J].Wireless Networks，2008，14（3）：347-355.

[5]Misra S，Hong S D，Xue G L，et al.Constrained relay node placement in wireless sensor networks：formulation and approximations [J].IEEE/ACM Transactions on Networking，2010，18（2）：434-447.

[6]Chelli A，Bagaa M，Djenouri D，et al.Onestep approach for twotiered constrained relay node placement in wireless sensor networks [J].IEEE Wireless Communications Letters，2016，5（4）：448-451.

[7]Gao Z P，Chen K，Qiu X S.Relay node placement with base stations in wireless sensor networks faulttolerant [J].Chinese Journal of Electronics，2014，23（4）：794-800.

[8]Lin G H，Xue G L.Steiner tree problem with minimum number of Steiner points and bounded edgelength [J].Information Processing Letters，1999，69（2）：53-57.

[9]Souissi M，Meddeb A.Modelling of clustering with relay nodes in Wireless Sensor Networks [C].Proceedings of the 7th Annual Computing and Communication Workshop and Conference，Las Vegas：IEEE，2017.

[10]Simon M K，Alouini M S.Digital communication over fading channels [M].2nd ed.Hoboken：Wiley，2005.

[11]Molisch A F.Wireless communications [M].Hoboken：Wiley，2005.

（責任編輯：包震宇，郁慧）