無線傳感器網(wǎng)絡(luò)中雙層受限中繼節(jié)點(diǎn)放置算法研究

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

摘要： 針對(duì)在三維空間中，對(duì)于中繼節(jié)點(diǎn)（RN）的位置受限并且是雙層拓?fù)涞那闆r，提出了一種基于混合整數(shù)線性規(guī)劃的中繼節(jié)點(diǎn)放置算法，該算法首先考慮三維空間中繼節(jié)點(diǎn)放置的物理層模型，然后基于混合整數(shù)線性規(guī)劃（MIPS）給出最優(yōu)能效的分簇，使得每個(gè)傳感器節(jié)點(diǎn)與相應(yīng)簇頭之間的傳輸距離最小.仿真結(jié)果表明：與只考慮最小化簇內(nèi)距離的中繼節(jié)點(diǎn)放置算法相比，本算法在降低重傳率和延長(zhǎng)網(wǎng)絡(luò)生命周期方面都有較大的改善.

關(guān)鍵詞：

中繼節(jié)點(diǎn)； 無線傳感器網(wǎng)絡(luò)； 雙層受限； 整數(shù)線性規(guī)劃

中圖分類號(hào)： TN 929.5文獻(xiàn)標(biāo)志碼： A文章編號(hào)： 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

基金項(xiàng)目： 上海市自然科學(xué)基金項(xiàng)目（16ZR1424500）

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

導(dǎo)師簡(jiǎn)介： 周小平（1981-），男，博士，副教授，主要從事寬帶無線通信、新一代移動(dòng)通信和物聯(lián)網(wǎng)技術(shù)方面的研究.Email：zxpshnu@163.com

*通信作者

引用格式： 向浩凱，周小平，王家南，等.無線傳感器網(wǎng)絡(luò)中雙層受限中繼節(jié)點(diǎn)放置算法研究 [J].上海師范大學(xué)學(xué)報(bào)（自然科學(xué)版），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引言

網(wǎng)絡(luò)節(jié)點(diǎn)的合理布局是無線傳感器（WSN）網(wǎng)絡(luò)運(yùn)行的首要前提.在WSN的大多數(shù)應(yīng)用場(chǎng)景中，傳感器節(jié)點(diǎn)（SN）和網(wǎng)關(guān)節(jié)點(diǎn)（GN）的布局位置相對(duì)固定，并且它們的能量往往難以補(bǔ)充，為了延長(zhǎng)網(wǎng)絡(luò)生命周期，提升網(wǎng)絡(luò)連通性與可靠性，可以通過放置中繼節(jié)點(diǎn)（RN）的方式來實(shí)現(xiàn)[1].因此，中繼節(jié)點(diǎn)布局的優(yōu)劣往往決定了無線傳感器網(wǎng)絡(luò)的生命周期、通信質(zhì)量[2].

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

文獻(xiàn)[6]提出了一步受限RN放置算法，保證SN與基站相連接的情況下放置最小數(shù)量的中繼節(jié)點(diǎn).針對(duì)文獻(xiàn)[6]沒有考慮網(wǎng)絡(luò)的容錯(cuò)性能，文獻(xiàn)[7]和[8]在滿足網(wǎng)絡(luò)容錯(cuò)需求的情況下，基于Steiner樹的理論給出最小數(shù)量放置RN的探索式算法.

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

1系統(tǒng)模型

本研究場(chǎng)景的系統(tǒng)模型如圖1所示，其中RN作為簇頭，負(fù)責(zé)收集來自SN的數(shù)據(jù)并將其轉(zhuǎn)發(fā)到基站，對(duì)于此問題，需要找到最優(yōu)化的RN部署方案，使每一個(gè)傳感器都與基站連接.

基站與基站之間是通過有線的方式連接的，u代表發(fā)射節(jié)點(diǎn)，v代表接收節(jié)點(diǎn)，發(fā)射功率分別為Pu和Pv，兩個(gè)節(jié)點(diǎn)之間的信道增益為au，v，瑞利塊衰落在同一個(gè)塊中信道增益保持常量.在本系統(tǒng)中，考慮了其他節(jié)點(diǎn)對(duì)節(jié)點(diǎn)v的干擾，節(jié)點(diǎn)w對(duì)節(jié)點(diǎn)v的衰減系數(shù)為aw，v，服從瑞利分布.從節(jié)點(diǎn)v所獲得的接收信號(hào)

2雙層受限RN放置算法

為了能夠最優(yōu)化放置RN，減少所提方案的復(fù)雜度，假設(shè)節(jié)點(diǎn)u的發(fā)射范圍為ρu，它的大小由節(jié)點(diǎn)發(fā)射功率決定，也就是說當(dāng)節(jié)點(diǎn)v與節(jié)點(diǎn)u之間的距離不超過ρu，那么節(jié)點(diǎn)u就能把節(jié)點(diǎn)v選作為父節(jié)點(diǎn).

由（4），（5）式可知，節(jié)點(diǎn)v的平均接收信噪比

其中Cw，v=∏z≠u，v，wz∈Nγ—w，vγ—w，v-γ—z，v，Y表示隨機(jī)事件，y表示隨機(jī)事件中的一個(gè)具體事例，N表示發(fā)射節(jié)點(diǎn)的集合.

為了提升WSN在運(yùn)行過程中的通信質(zhì)量，減小節(jié)點(diǎn)的死亡速度，目標(biāo)是將SN分配到最接近的RN，使成員節(jié)點(diǎn)的能量消耗最小.在滿足通信要求的情況下，部署最少數(shù)量的RNs以覆蓋所有的傳感區(qū)域是首要目標(biāo).為了得到RN的最優(yōu)化放置位置，考慮了通信質(zhì)量、網(wǎng)絡(luò)覆蓋范圍和信號(hào)接收概率.通過將SN分配到最接近的RN，最大限度提高WSN的壽命，解決集群形成的問題，最終將問題轉(zhuǎn)化成簇內(nèi)通信距離最小化的問題.

WSN能量的消耗將會(huì)隨成員節(jié)點(diǎn)與其對(duì)應(yīng)RN距離的增加而增大.其距離

其中（xu，yu，hu），（Xv，Yv，Hv）是節(jié)點(diǎn)su和中繼節(jié)點(diǎn)RNv的坐標(biāo).

假設(shè)傳感范圍是面積為B的正方形區(qū)域，則節(jié)點(diǎn)u的最大通信半徑為ρu，可以覆蓋的區(qū)域面積為πρ2u.

令αuv為每個(gè)傳感器節(jié)點(diǎn)分配給相應(yīng)簇頭的判斷因子，它是一個(gè)布爾型變量，當(dāng)節(jié)點(diǎn)su所對(duì)應(yīng)的簇頭是RNv時(shí)，αuv=1；否則αuv=0.

在確保通信質(zhì)量的情況下，使網(wǎng)絡(luò)的數(shù)據(jù)傳輸距離最小.即求

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

3結(jié)果仿真與分析

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

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

4結(jié)論

針對(duì)在雙層受限結(jié)構(gòu)的WSN中，傳統(tǒng)的RN放置算法會(huì)導(dǎo)致丟包率高和網(wǎng)絡(luò)生命周期短的問題，本文作者提出了基于MIPS的RN放置算法.該算法考慮了RN放置的物理層因素，改善了網(wǎng)絡(luò)通信質(zhì)量，提升了傳包效率，延長(zhǎng)了WSN的生命周期.因此對(duì)于雙層受限結(jié)構(gòu)的WSN來說，本算法是一種較好的RN放置方案.

參考文獻(xiàn)：

[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.

（責(zé)任編輯：包震宇，郁慧）