• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看

      ?

      基于最優(yōu)化的能耗均衡分簇路由協(xié)議

      2020-06-22 13:15:56趙東方施偉斌
      軟件導刊 2020年5期
      關鍵詞:最優(yōu)化線性規(guī)劃無線傳感器網絡

      趙東方 施偉斌

      摘 要:為了均衡傳統(tǒng)分簇路由算法中的簇間傳輸能耗,減少簇首更換開銷,提出基于最優(yōu)化模型的能耗均衡分簇路由協(xié)議opt_leach。將區(qū)域節(jié)點劃分成大小相同的簇,均衡不同簇的簇內通信開銷;簇間通信采用多種路由組合的方式通信,均衡簇間通信開銷;簇內節(jié)點可以連續(xù)充當簇首,減少簇首更換開銷。實驗結果表明,與傳統(tǒng)分簇路由算法相比,該算法可更好地實現(xiàn)能耗均衡,延長網絡生存時間。

      關鍵詞:無線傳感器網絡;分簇路由協(xié)議;能耗均衡;最優(yōu)化;線性規(guī)劃

      DOI:10. 11907/rjdk. 191936 開放科學(資源服務)標識碼(OSID):

      中圖分類號:TP393文獻標識碼:A 文章編號:1672-7800(2020)005-0204-05

      0 引言

      無線傳感器網絡(WSN)廣泛應用于醫(yī)療保健、污染監(jiān)測和目標跟蹤系統(tǒng)等領域[1]。WSN由大量節(jié)點組成,其計算、傳感和無線通信能力有限,能效是一個重要問題,直接影響到WSN的網絡壽命[2]。與非聚類協(xié)議相比,聚類通??梢詼p少沖突和空閑偵聽造成的能量耗散。因為在每個集群中,簇首都會為每個節(jié)點分配一個獨占的時間槽,從而避免沖突。此外,節(jié)點不需要在每個時分多址(TDMA)幀中保持清醒,只需要在其特定的時隙中保持清醒[3]。因此,集群是延長WSN網絡生存期的常用策略。

      為解決WSN中能量均衡高效問題,Heinzelman等[4]提出了最早的分簇路由協(xié)議。該協(xié)議充分利用數(shù)據(jù)融合技術,是分簇路由協(xié)議的代表;HEED[5]協(xié)議采用迭代的方式選取簇首,并考慮了節(jié)點的剩余能量、通信代價和網絡中簇首的分布,避免能量少的節(jié)點過早死亡,延長了網絡生存時間;李成法等[6]提出EEUC協(xié)議,將網絡組織成大小非均勻的簇,以解決多跳路由傳感器網絡中常見的“熱區(qū)”問題,但未說明多跳路由路徑的建立過程;黃利曉等[7]提出通過加入間距因子、剩余能量因子和節(jié)點密度因子改進簇首選擇概率函數(shù)的閾值計算式,綜合考慮節(jié)點剩余能量和地理位置選擇簇首,取得了一些改進效果;胡源等[8]通過對監(jiān)測區(qū)域的等間距環(huán)形劃分和等夾角扇形劃分,選擇同一扇形區(qū)域內的下一跳節(jié)點以保證源節(jié)點與基站的通信距離最短;UCF[9]協(xié)議提出一種基于模糊邏輯的不等聚類方法,改進了非均勻成簇的半徑確定,進一步均衡了簇間通信;Peyman Neamatollahi等[10]提出了一種基于動態(tài)超循環(huán)策略(DHRP)的能量感知集群算法SEDC,通過減少頻繁重新聚類的開銷延長集群WSN中的網絡生存期,但是沒有對簇首持續(xù)輪數(shù)進行理論推導。

      傳統(tǒng)的分簇方法采用概率競爭的方式選擇簇首,每一輪簇首分布情況未知,因此難以對簇間通信建立能耗均衡路由規(guī)劃,導致不同區(qū)域的簇首傳輸能耗不均衡;同時,每個節(jié)點當選簇首的持續(xù)時間較短,增加了更換簇首的開銷。為此,本文提出一種基于最優(yōu)化模型的能耗均衡分簇路由協(xié)議opt_leach。首先將區(qū)域節(jié)點均勻劃分成大小相同的簇,保證網絡各個簇的簇內通信消耗均衡;其次簇間通信采用多種路由組合方式,使用線性規(guī)劃求解每種路由方式的最優(yōu)比例。在每一個簇內,使用線性規(guī)劃求解每個節(jié)點充當簇首的最優(yōu)輪數(shù),使得節(jié)點可以連續(xù)充當簇首,從而減少了重新聚類的頻率和開銷。仿真實驗表明,與傳統(tǒng)分簇路由算法相比,本文提出的opt_leach算法可以更好地實現(xiàn)能耗均衡并延長網絡生存時間。

      1 分簇路由模型介紹

      為便于比較,本文采用分簇路由協(xié)議研究中的典型分析模型[4,7,10-12],對網絡模型和硬件能耗模型作出假設與約束。

      1.1 傳感器節(jié)點模型

      (1)傳感器節(jié)點隨機、相對均勻分布在規(guī)則圖形的監(jiān)測區(qū)域中。

      (2)所有的傳感器節(jié)點具有相同的數(shù)據(jù)處理能力和通信能力,初始能量相同。

      (3)傳感器節(jié)點被隨機分散后位置固定,網絡部署后不再進行人為干涉。

      (4)傳感器節(jié)點可以知悉自身剩余能量,位置可被知悉。

      (5)節(jié)點部署具有冗余度,一定區(qū)域范圍內節(jié)點間的數(shù)據(jù)可以進行數(shù)據(jù)融合。

      (6)節(jié)點可以根據(jù)數(shù)據(jù)需要發(fā)送的距離調整發(fā)射功率。

      1.2 硬件能耗模型

      (1)發(fā)送l bit數(shù)據(jù)能耗。當l bit的數(shù)據(jù)需要傳輸時,節(jié)點所消耗的能量主要由兩部分組成:發(fā)送l bit數(shù)據(jù)的基本能量耗損以及功率放大電路的能量耗損;同時,針對不同的發(fā)射距離d選擇不同的發(fā)送功率。

      當傳輸距離為d時,功率放大器所消耗的能量需要依據(jù)發(fā)送器與接收器的距離d與閾值d0進行比較。其中,[d0=εfsεamp]是區(qū)分兩種消耗的閾值。當傳輸間距dd0時使用第二種模式。

      (2)接收l bit數(shù)據(jù)能耗:Erv(l,d)=l×Eelec。

      (3)數(shù)據(jù)融合l bit數(shù)據(jù)能耗:Eag(l,d)=l×Eelec。

      2 協(xié)議及算法介紹

      Opt_leach協(xié)議是一種集中式和分布式相結合的并行成簇算法。

      初始階段:sink收集節(jié)點的位置信息和能量信息:①將節(jié)點均勻分簇,每個節(jié)點分配一個固定的簇編號,此后節(jié)點所屬的簇編號不再改變;②計算不同編號的簇間通信路由組合最佳比例,寫入路由表;③計算每個簇內節(jié)點充當簇首的順序和最優(yōu)持續(xù)輪數(shù),寫入簇首順序表;④sink節(jié)點將以上結果分發(fā)至每個節(jié)點。初始階段只執(zhí)行一次。

      分布式階段:①每個初始簇首為簇首順序表的第一個節(jié)點,相同簇編號的節(jié)點加入同一個簇,簇首為每個成員分配TDMA時隙;②簇首更換:簇首輪數(shù)若達到最優(yōu)輪數(shù),則指定簇首順序表的下一個節(jié)點在下一輪成為簇首,并使用該節(jié)點的TDMA時隙,簇內其它節(jié)點TDMA時隙不變;③簇間通信:簇首節(jié)點按照事先分配的路由表中的路由路徑傳輸數(shù)據(jù)至sink節(jié)點。

      2.1 均勻分簇

      因為節(jié)點位置固定,所以可對節(jié)點進行區(qū)域劃分[6,9,13-16]。本文對節(jié)點區(qū)域均勻劃分,首先將節(jié)點按照相對于匯聚節(jié)點在垂直方向上劃分成Y個區(qū)域,再將水平方向劃分成X個區(qū)域,這樣一共得到X×Y個區(qū)域。每個區(qū)域的節(jié)點獲得相同的簇編號,即每個區(qū)域的節(jié)點將始終在同一個簇內。圖1展示了100m×100m區(qū)域內在隨機均勻分布100節(jié)點情況下,節(jié)點被均勻分成4個簇的情形。

      2.2 簇間通信方式確定

      在LEACH協(xié)議中,每個簇首采用單跳直接與匯聚節(jié)點通信。當節(jié)點分布區(qū)域逐漸增大時,靠近匯聚節(jié)點的簇和遠離匯聚節(jié)點的簇能耗差異明顯,距sink節(jié)點較遠的簇節(jié)點能量會先耗盡。若簇首采用多跳方式往往會導致靠近sink節(jié)點的簇節(jié)點能量先耗盡[17-18]。因此,本文簇首間通信采用多種路由組合的方式傳輸數(shù)據(jù),并計算最優(yōu)比例。

      假設一共有n個簇首節(jié)點,每個節(jié)點用于簇首傳輸?shù)哪芰繛镋i,則簇首節(jié)點共有m(m=2n(n-1)/2)種可能路徑。圖2為當n=3時的路由情況,c節(jié)點有4種路徑選擇(c→b→a→sink,c→b→sink,c→a→sink,c→sink),b節(jié)點有兩種路徑選擇(b→a→sink,b→sink),a節(jié)點有一種路徑選擇(a→sink),則根據(jù)乘法規(guī)則,n=3時一共有4*2*1=8種路由方式。

      在每一輪中,簇首會從所有路由路徑中選擇一種作為簇首通信方式。若第i(1≤i≤n)個簇首在第k(1≤k≤m)種路由方式中傳輸一輪數(shù)據(jù)的能耗為CHcostik,則第k種路由方式的使用次數(shù)為lk輪。在每個簇首i用于傳輸數(shù)據(jù)的能量不超過Ei前提下,通過確定不同路由最優(yōu)比例獲得簇首可傳輸數(shù)據(jù)的最大輪數(shù)lmax,可使用最優(yōu)化模型中的線性規(guī)劃求解。

      當n逐漸增大時,求解出的路由組合可能有很多種。實際應用中可以忽略占比低于閾值Routeth的路由路徑,保留占比較大且切換較容易的幾種路由,再作一次線性規(guī)劃得到最優(yōu)比例,具體閾值和路由數(shù)量可根據(jù)實際情況作相應調整。

      2.3 簇內節(jié)點成為簇首的輪數(shù)和順序

      在均衡每個簇的簇首能耗后,區(qū)域中每個簇可以看成近似等價。在每個固定的簇中,不同位置節(jié)點當選簇首時節(jié)點能耗分布不同。為了均衡簇內每個節(jié)點的消耗,分析每個節(jié)點當選簇首的最優(yōu)輪數(shù)。

      2.3.1 節(jié)點成為簇首的輪數(shù)確定

      假設某個簇內一共有n個節(jié)點,每個節(jié)點的初始能量為E。由于單個簇內同時只有一個簇首,所以一共有n種成簇情況,即每個節(jié)點輪流當一次簇首。第j個節(jié)點在第i個節(jié)點當選簇首時的能耗 costij可由式(4)計算,其中i=j時,為節(jié)點當選簇首時使用多種路由組合的加權平均消耗。

      2.3.2 簇首順序確定

      當簇內節(jié)點i成為簇首的最優(yōu)輪數(shù)已知后,節(jié)點i在第k種路由方式下充當簇首的次數(shù)在沒有達到Rik之前的任何一輪都可以成為簇首。當節(jié)點i在第k種路由方式下成為簇首的次數(shù)達到Rik時,在第k種路由方式下不再成為簇首,所以簇首的順序確定可依據(jù)實際應用靈活變化。

      本文將簇內節(jié)點i到sink的距離di作為簇首節(jié)點的順序指標。在第k種路由方式下,di小的節(jié)點先成為簇首,并且連續(xù)充當簇首Rik輪,即節(jié)點連續(xù)充當簇首的輪數(shù)為當前路由方式的最優(yōu)輪數(shù)。這樣做的好處是簇首不必頻繁切換,有利于路由的穩(wěn)定并降低控制信息的能耗。當整個簇內節(jié)點執(zhí)行完當前路由方式的輪數(shù)后,整體切換成路由表中的下一種路由方式。

      3 仿真分析

      本文在Matlab平臺上對LEACH、HEED、SEDC和本文的opt_leach協(xié)議分別進行仿真。假設100個節(jié)點隨機均勻分布在從(0,0)到(100m,100m)的網絡區(qū)域內[4,7,11-12],匯聚節(jié)點部署在網絡區(qū)域之外的坐標(50m,175m)。為了保證區(qū)域的連通性[5],本文假設每間隔10m×10m方形區(qū)域內至少有一個節(jié)點,因為連通性是保障節(jié)點可以通過多跳的方式傳輸數(shù)據(jù)的重要條件,在實際應用中這個假設也是合理且易于實現(xiàn)的。表1列出了實驗參數(shù)。

      3.1 opt_leach參數(shù)計算

      區(qū)域劃分的參數(shù)為x=2,y=2,即簇首的最大跳數(shù)為2,節(jié)點共有兩種路由選擇。通過計算得到兩種路由方式的最佳比例為單跳Route1=0.401 9,多跳Route2=0.598 1。4個簇計算出的多跳輪數(shù)分別為577、580、580、576,單跳輪數(shù)分別為385、387、385、386。將不同區(qū)域的輪數(shù)統(tǒng)一為計算出的最小值,得到最終每個區(qū)域的節(jié)點將以576輪簇首多跳路由和385輪簇首單跳通信,共持續(xù)961輪。單個簇內每個節(jié)點的輪數(shù)如圖3所示。

      在到達最大可持續(xù)輪數(shù)后,節(jié)點會相繼死亡,opt_leach協(xié)議著重于節(jié)點全部存活時傳輸數(shù)據(jù)的能耗均衡最優(yōu)化,所以未對節(jié)點相繼失效時的分簇進行討論。為了便于與其它協(xié)議進行對比,在節(jié)點到達最大可持續(xù)輪數(shù)后,采用SEDC[10]協(xié)議對剩余節(jié)點進行分簇。

      3.2 協(xié)議對比與分析

      通過比較執(zhí)行完opt_leach的最大輪數(shù)后,將每個協(xié)議的節(jié)點存活數(shù)量和每一輪能耗速率作為評估opt_leach協(xié)議性能指標,并對opt_leach協(xié)議的能耗均衡性和可預測性展開分析。

      3.2.1 節(jié)能性對比

      由圖4可知,當輪數(shù)達到961時,opt_leach協(xié)議的節(jié)點全部存活,符合最大可持續(xù)輪數(shù)的計算結果。opt_leach的第一個節(jié)點死亡(FND)出現(xiàn)在第962輪,而SEDC、HEED和LEACH的FND分別出現(xiàn)在915、709和624輪;SEDC、HEED和LEACH的最后一個節(jié)點死亡(LND)分別在1016、935、941和1126輪。從圖5可知,opt_leach協(xié)議能量衰減曲線一直保持較小的斜率,這是因為在opt_leach協(xié)議算法中,節(jié)點在選擇簇間路由方式比例和簇內節(jié)點充當簇首的輪數(shù)都是線性規(guī)劃的最優(yōu)解,且固定簇首可以減少因為頻繁更換簇首而帶來的控制消息能耗。

      3.2.2 opt_leach協(xié)議能耗均衡性分析

      圖6是961輪之后每個節(jié)點的剩余能量,100個節(jié)點中大部分節(jié)點的剩余能量在0.02J左右,具有高度的能量均衡性。只有2個節(jié)點剩余能量較高,其中最高的約為0.06J。這是因為即使將區(qū)域節(jié)點均勻分成4個固定簇,每個簇的內部節(jié)點位置也不可能完全相同,最終每個簇計算出的最大可持續(xù)輪數(shù)會有微小差異。最終統(tǒng)一將輪數(shù)設置為不同區(qū)域中計算出的最小值,此時個別節(jié)點依然可以充當幾輪簇首,最終這些節(jié)點能量會略高于其它節(jié)點。

      4 結語

      本文針對分簇路由協(xié)議提出一種改進算法——opt_leach協(xié)議,其思想是使用最優(yōu)化模型中的線性規(guī)劃計算簇間不同路由組合的最優(yōu)比例,以及簇內節(jié)點充當簇首的最優(yōu)輪數(shù)。實驗結果表明,使用最優(yōu)化方法確定分簇路由協(xié)議中的簇間傳輸路徑和選擇簇首,可以降低網絡總能耗,延長網絡整體壽命。

      參考文獻:

      [1] LIU X X. Atypical hierarchical routing protocols for wireless sensor networks: a review[J]. ?IEEE Sensors Journal, 2015, 15(10): 5372-5383.

      [2] KHAN I, BELQASMI F,GLITHO R, et al. Wireless sensor network virtualization: a survey[J]. ?IEEE Communications Surveys and Tutorials, 2016, 18(1): 553-576.

      [3] FADEL, ETIMAD, GUNGOR ?V C, et al. A survey on wireless sensor networks for smart grid[J]. ?Computer Communications, 2015, 71(1): 22-33.

      [4] HEINZELMAN W B, CHANDRAKASAN A P, BALAKRISHNAN H. An application-specific protocol architecture for wireless microsensor networks[J]. ?IEEE Transactions on Wireless Communications, 2002, 1(4): 660-670.

      [5] YOUNIS O, FAHMY ?S. HEED: a hybrid, energy-efficient, distributed clustering approach for ad ? hoc sensor networks[J]. ?IEEE Transactions on Mobile Computing, 2004, 3(4): 366-379.

      [6] 李成法,陳貴海,葉懋,等. 一種基于非均勻分簇的無線傳感器網絡路由協(xié)議[J]. 計算機學報,2007,30(1):27-36.

      [7] 黃利曉,王暉,袁利永,等. 基于能量均衡高效WSN的LEACH協(xié)議改進算法[J]. 通信學報,2017,38(Z2):164-169.

      [8] 胡源,牛玉剛,鄒媛媛. 基于區(qū)域劃分的WSN非均勻多跳分簇路由算法[J]. 控制與決策,2017,32(9):1695-1700.

      [9] NEAMATOLLAHI P,NAGHIBZADEH M. Distributed unequal clustering algorithm in large-scale wireless sensor networks using fuzzy logic[J]. ?Journal of Supercomputing, 2018, 74(6): 2329-2352.

      [10] NEAMATOLLAHI, PEYMAN, NAGHIBZADEH, et al. Distributed clustering-task scheduling for wireless sensor networks using dynamic hyper round policy[J]. ?IEEE Transactions on Mobile Computing, 2018, 17(2): 334-347.

      [11] WANG A M,YANG D L,SUN D Y. A clustering algorithm based on energy information and cluster heads expectation for wireless sensor networks[J]. ?Computers & Electrical Engineering, 2012, 38(3): 662-671.

      [12] ZHU X R,SHEN L F,YUM TAK-SHING PETER. Hausdorff clustering and minimum energy routing for wireless sensor networks[J]. ?IEEE Transactions on Vehicular Technology,2009,58(2): 990-997.

      [13] GOU H S,YOO Y W. An energy balancing leach algorithm for wireless sensor networks[C]. Information Technology: New Generations (ITNG),2010 Seventh International Conference on,2010:822-827.

      [14] 孫彥清,彭艦,劉唐,等. 基于動態(tài)分區(qū)的無線傳感器網絡非均勻成簇路由協(xié)議[J]. 通信學報,2014,35(1):198-206.

      [15] 余秀雅,劉東平,楊軍. 基于K-means++的無線傳感網分簇算法研究[J]. 計算機應用研究,2017,34(1):181-185.

      [16] 張雅瓊. 基于K-Means的無線傳感網均勻分簇路由算法研究[J]. 控制工程,2015,22(6):1181-1185.

      [17] 劉述鋼,劉宏立,詹杰,等. 無線傳感網絡中能耗均衡的混合通信算法研究[J]. 通信學報,2009,30(1):12-17.

      [18] 孫勇,景博,張宗麟,等. 分簇路由的無線傳感器網絡通信模式與能量有效性研究[J]. 電子與信息學報,2007,29(9):2262-2264.

      (責任編輯:杜能鋼)

      猜你喜歡
      最優(yōu)化線性規(guī)劃無線傳感器網絡
      新課程概率統(tǒng)計學生易混淆問題
      東方教育(2016年10期)2017-01-16 20:33:22
      基于多樞紐輪輻式運輸網絡模型的安徽省快遞網絡優(yōu)化
      價值工程(2016年36期)2017-01-11 19:43:04
      小議初中語文課堂教學的導入
      未來英才(2016年19期)2017-01-04 11:15:38
      基于學習效果最優(yōu)化的民辦高校教學改革措施芻議
      一種改進的基于RSSI最小二乘法和擬牛頓法的WSN節(jié)點定位算法
      線性規(guī)劃常見題型及解法
      首都機場安全環(huán)建設與管理分析
      價值工程(2016年31期)2016-12-03 22:17:04
      最優(yōu)化,永遠的教學追求
      無線傳感器網絡定位技術可靠性分析
      軟件導刊(2016年9期)2016-11-07 17:46:50
      對無線傳感器網絡MAC層協(xié)議優(yōu)化的研究與設計
      科技視界(2016年22期)2016-10-18 15:25:08
      精河县| 水城县| 长岭县| 文昌市| 盐边县| 青海省| 和林格尔县| 田阳县| 获嘉县| 丹阳市| 开封县| 峡江县| 马关县| 平泉县| 柳江县| 平和县| 蛟河市| 兴安县| 任丘市| 江源县| 延吉市| 鄂温| 陆丰市| 卓尼县| 莒南县| 正安县| 甘南县| 赤峰市| 普安县| 宁化县| 德惠市| 贵阳市| 普安县| 石台县| 桓台县| 江山市| 南汇区| 万安县| 宁明县| 含山县| 伊金霍洛旗|