基于無線信號不規(guī)則性的無線傳感網(wǎng)層次型拓?fù)淇刂扑惴?/h1>
2015-12-13 11:47:26王惠珠
電子與信息學(xué)報 2015年9期
唐 宏 王惠珠
1 引言
無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks,WSNs）由大量能量受限的傳感器設(shè)備組成，延長網(wǎng)絡(luò)生存時間是目前首先需要考慮的問題[1,2]。拓?fù)淇刂剖且环N重要的節(jié)能技術(shù)，在保證覆蓋和連通質(zhì)量的條件下，通過減少冗余鏈路降低網(wǎng)絡(luò)能耗[3]。層次型拓?fù)淇刂扑惴ù蠖家訪EACH算法為基礎(chǔ)發(fā)展而來，其拓?fù)浣Y(jié)構(gòu)主要有3類：（1）簇內(nèi)單跳、簇間單跳[4,5]；（2）簇內(nèi)多跳、簇間多跳[6]；（3）單多跳相結(jié)合[7,8]。其中實(shí)現(xiàn)分簇的方法主要有靜態(tài)分簇[6,9]和動態(tài)分簇。選取簇頭的方式主要有4類：（1）采用隨機(jī)數(shù)閾值，使產(chǎn)生的隨機(jī)數(shù)小于該閾值的節(jié)點(diǎn)成為簇頭[4,5]。（2）考慮節(jié)點(diǎn)剩余能量，使剩余能量較高的節(jié)點(diǎn)優(yōu)先成為簇頭[8]。（3）考慮節(jié)點(diǎn)競爭半徑，使基站附近形成較小的簇，緩解基站附近的“熱區(qū)”問題[7,8]。（4）綜合考慮節(jié)點(diǎn)剩余能量以及到基站的距離，使剩余能量較高且距離基站較近的節(jié)點(diǎn)優(yōu)先成為簇頭[10]。
上述方法未考慮節(jié)點(diǎn)成為簇頭后簇結(jié)構(gòu)的性能，且未考慮無線信號不規(guī)則性對拓?fù)錁?gòu)建過程的影響。延長網(wǎng)絡(luò)生存時間的同時未兼顧網(wǎng)絡(luò)能量均衡性，且存在簇頭間鏈路較稀疏的情況。本文欲在考慮無線信號不規(guī)則性的條件下，對節(jié)點(diǎn)成為簇頭后的簇結(jié)構(gòu)穩(wěn)定性建模，并使簇頭間形成平面型數(shù)據(jù)轉(zhuǎn)發(fā)層，構(gòu)建兩層的WSNs拓?fù)浣Y(jié)構(gòu)。該方法首先根據(jù)無線信號不規(guī)則性 DOI（Degree Of Irregularity）模型[11]定義區(qū)域分割參數(shù)實(shí)現(xiàn)靜態(tài)分簇。其次，根據(jù)節(jié)點(diǎn)成簇穩(wěn)定性選取候選簇頭，并根據(jù)候選簇頭在簇內(nèi)的位置確定最終簇頭。簇頭間則形成平面型拓?fù)浣Y(jié)構(gòu)以避免由于中繼簇頭突然失效造成的網(wǎng)絡(luò)分割。最后給出WSIBTC算法與其他幾類算法的實(shí)驗比較結(jié)果。
2 系統(tǒng)假設(shè)和能耗模型
2.1 系統(tǒng)假設(shè)
（1）傳感器節(jié)點(diǎn)隨機(jī)分布于監(jiān)測區(qū)域內(nèi)，基站位于監(jiān)測區(qū)域之外；
（2）傳感器節(jié)點(diǎn)和基站部署完成后處于靜止?fàn)顟B(tài)，前者同構(gòu)，能量受限，后者能量無限；
（3）傳感器節(jié)點(diǎn)通過現(xiàn)有的定位技術(shù)或者接收信號強(qiáng)度與節(jié)點(diǎn)間距離的關(guān)系獲得自身在監(jiān)測區(qū)域內(nèi)的具體位置信息。
定義 1 WSNs可以抽象為2維平面圖G （V, E）。其中G為節(jié)點(diǎn)以最大發(fā)射功率相互通信時形成的原始拓?fù)浣Y(jié)構(gòu)，V為節(jié)點(diǎn)集合，E為節(jié)點(diǎn)間邊的集合。
定義 2 集合 VPH包含的元素為任意節(jié)點(diǎn)的物理鄰居節(jié)點(diǎn)。對于任意的節(jié)點(diǎn)i,j∈V，若滿足i∈且 j ∈，則表示節(jié)點(diǎn)i和j相互覆蓋；如果i∈且j?VPiH，則表示節(jié)點(diǎn)i覆蓋j，但是節(jié)點(diǎn)j不能覆蓋i。
定義 3 集合VL包含的元素為任意節(jié)點(diǎn)的邏輯鄰居節(jié)點(diǎn)。該集合是通過某種計算規(guī)則，將節(jié)點(diǎn)VPH集合中符合條件的物理鄰居節(jié)點(diǎn)篩選出來組成的節(jié)點(diǎn)集合。
定義5Ri為節(jié)點(diǎn)i的平均有效傳輸距離，Rj為節(jié)點(diǎn)j的平均有效傳輸距離， dij為節(jié)點(diǎn)i, j之間的距離，如果dij＜Ri且Rj，則i∈且j∈。
2.2 能耗模型
WSIBTC算法采用與LEACH算法相同的能耗模型。任意兩個可以相互通信且距離為d的節(jié)點(diǎn)間發(fā)送l比特數(shù)據(jù)的能耗為
其中 Ee表示發(fā)射端和接收端的電路損耗能量；d0為參考距離，滿足d0=。LEACH能耗模型定義如果 d ＜d0，功率放大損耗采用自由空間傳播模型；如果 d ≥d0，則采用多徑傳播模型。εfs和εmp分別表示兩種模型中對應(yīng)的功率放大器的放大參數(shù)。令DAE 為節(jié)點(diǎn)融合數(shù)據(jù)包時消耗的能量，則接收端接收l比特數(shù)據(jù)以及節(jié)點(diǎn)將接收到的0n個數(shù)據(jù)包融合為一個數(shù)據(jù)包時的能耗分別可用式（2），式（3）表示為
3 算法原理
3.1 子區(qū)域個數(shù)的確定
文獻(xiàn)[11]建立的無線信號不規(guī)則性數(shù)學(xué)模型為DOI模型，即由于傳感器設(shè)備本身的異構(gòu)性或者信號傳播時發(fā)生的衍射、反射等現(xiàn)象造成無線信號在不同傳播方向上具有不同的路徑損耗。DOI模型中節(jié)點(diǎn)各方向上的有效傳輸距離為
其中 Pt為節(jié)點(diǎn)發(fā)射功率；rss為接收端接收信號強(qiáng)度；Pl（d0）為自由空間傳播模型下的路徑損耗；α為路徑損耗指數(shù)，介于2～4之間。 ki為具體傳播方向上的路徑損耗調(diào)整因子，滿足其中DOI為傳播方向每改變1°時最大路徑損耗變化百分?jǐn)?shù)，介于0～0.02之間；Rand為服從韋伯分布的隨機(jī)數(shù)； i = 0 代表初始傳播方向。由于節(jié)點(diǎn)可以通過測量獲取接收信號強(qiáng)度，為了便于分析，將式（4）化簡為
令 Rmax表示節(jié)點(diǎn)最大有效傳輸距離， Rmin為最小有效傳輸距離，則節(jié)點(diǎn)平均有效傳輸距離為R = （Rmax+Rmin）/2。假設(shè)節(jié)點(diǎn)隨機(jī)分布于邊長為L的正方形區(qū)域中，子區(qū)域個數(shù)為m，則每個子區(qū)域的面積約為 L2/m。由正方形面積與對角線間的關(guān)系可得，子區(qū)域?qū)蔷€長度l0= L，則簇內(nèi)及相鄰子區(qū)域節(jié)點(diǎn)相互可達(dá)的條件為2l0≤R，因此m與R的關(guān)系需滿足 m ≥ 8L2/f2（kav）。其中 kav為R對應(yīng)的平均路徑損耗調(diào)整因子。綜上所述，區(qū)域分割參數(shù) t0需滿足
?表示向上取整?；靖鶕?jù)t0將監(jiān)測區(qū)域分別進(jìn)行橫向、縱向上的劃分，則 m =。
3.2 簇頭的確定
串聯(lián)與并聯(lián)模塊的組合可以描述任何復(fù)雜系統(tǒng)。在層次型網(wǎng)絡(luò)拓?fù)渲?，根?jù)節(jié)點(diǎn)感知到的數(shù)據(jù)間的依賴關(guān)系，其 RBD （Reliability Block Diagram）模型可以表示為[12]
圖1 有n個簇成員的簇頭RBD模型
節(jié)點(diǎn)i競爭簇頭時的成簇穩(wěn)定性可以表示為
其 中S（ r） 為 節(jié) 點(diǎn) 的 生 存 函 數(shù) ， 定 義 為Si（ r）=Ere（r）（r）。其中（r）為節(jié)點(diǎn)i第r輪的剩余能量，Ere（r）為第r輪網(wǎng)絡(luò)平均剩余能量。
候選簇頭的產(chǎn)生是形成簇結(jié)構(gòu)的基礎(chǔ)。子區(qū)域中的節(jié)點(diǎn)均產(chǎn)生一個0～1之間的隨機(jī)數(shù)，若節(jié)點(diǎn)i產(chǎn)生的隨機(jī)數(shù)小于等于閾值T（ i），則廣播其為候選簇頭的消息?，F(xiàn)有文獻(xiàn)對LEACH算法中T（ i）的改進(jìn)主要通過引入節(jié)點(diǎn)剩余能量以及全網(wǎng)平均剩余能量。當(dāng)網(wǎng)絡(luò)進(jìn)入瓶頸期，存活節(jié)點(diǎn)較低的能量等級使T（ i）大大減小，造成簇頭選取過程的不穩(wěn)定[9]。考慮上述因素，一種新的閾值計算公式可以表示為
其中p為節(jié)點(diǎn)成為簇頭的概率，r是目前循環(huán)進(jìn)行的輪數(shù)，0G為最近1/p輪中尚未成為簇頭的節(jié)點(diǎn)集合。產(chǎn)生的隨機(jī)數(shù)小于等于（）T i的簇成員將成為候選簇頭，廣播COMPETE_HEAD_MSG。
簇頭在簇中的位置直接影響著簇成員的能耗。假設(shè)每個簇中距離基站最近和最遠(yuǎn)的節(jié)點(diǎn)分別為i,j,ijd為節(jié)點(diǎn)i,j之間的距離。以ijd為直徑畫圓，候選簇頭y,h,g的位置如圖2所示。根據(jù)三角公式，位于該圓域內(nèi)且距離節(jié)點(diǎn)i,j最近的候選簇頭將優(yōu)先成為最終簇頭。
競選成功的候選簇頭廣播 FINAL_HEAD_MSG，接收到該消息的候選簇頭則廣播 QUIT_MSG宣布競爭失敗，成為簇成員。簇成員發(fā)送JOIN_MSG消息請求入簇，建立簇內(nèi)星型拓?fù)浣Y(jié)構(gòu)。
3.3 簇頭間權(quán)值函數(shù)的確定
圖2 候選簇頭位置示意圖
網(wǎng)絡(luò)中的節(jié)點(diǎn)可以被看作粒子，節(jié)點(diǎn)間的通信代價可以等效為粒子間的作用力[13]。WSIBTC算法將這種虛擬的作用力定義為節(jié)點(diǎn)間的“粘度”，其中簇頭的剩余能量等效為粒子的電荷量，簇頭間的路徑損耗作為簇頭通信時的代價，則簇頭間的“粘度”滿足
dBS為簇頭到基站的距離，γ1,γ2為加權(quán)系數(shù)，滿足γ1+γ2=1。
構(gòu)建簇頭間的拓?fù)浣Y(jié)構(gòu)時，簇成員暫時關(guān)閉通信模塊進(jìn)入睡眠狀態(tài)。簇頭廣播HelloMSG獲取鄰居信息表。簇頭i接收到鄰居簇頭j的信息表后，首先判斷是否存在公共物理鄰居簇頭s。若存在，則需比較W（ i, j） 與W（ i, s） + W （ s, j ） 的大小，判斷與物理鄰居進(jìn)行通信時的本地最小權(quán)值。令VLiS為簇頭i的單跳邏輯鄰居簇頭集合， VLiM為多跳邏輯鄰居簇頭集合，若存在公共物理鄰居簇頭s滿足W（ i, j）＞W(wǎng)（ i, s） + W （ s, j） ，則VLiM= VLiM∪ { j}且中繼簇頭為s，否則 VLiS
= VLiS∪{ j }。所有簇頭均執(zhí)行上述過程，建立平面型數(shù)據(jù)轉(zhuǎn)發(fā)層。
3.4 網(wǎng)絡(luò)能耗分析
假設(shè)監(jiān)測區(qū)域為邊長為L的正方形區(qū)域，節(jié)點(diǎn)數(shù)為 N0,n為子區(qū)域中節(jié)點(diǎn)個數(shù)，初始能量為 E0,m為子區(qū)域個數(shù)，每輪網(wǎng)絡(luò)能耗包括簇頭能耗 ECH和簇成員能耗 ECM。令網(wǎng)絡(luò)每輪能耗為 Erd，則 Erd=ECH+ECM。WSIBTC算法根據(jù)簇頭到基站的距離選取負(fù)責(zé)與基站直接通信的簇頭，其選擇依據(jù)為le=（dBS/ d0），其中 ? 為向上取整函數(shù)。若le＞1，即該簇頭與基站間的距離大于 d0，需通過中繼簇頭轉(zhuǎn)發(fā)數(shù)據(jù)；若le = 1 ，即該簇頭到基站的距離小于等于 d0。le = 1 的簇頭廣播自身的等級消息，其他簇頭則將相應(yīng)簇頭標(biāo)記為最終目的節(jié)點(diǎn)，使網(wǎng)絡(luò)中傳遞的數(shù)據(jù)包最終由該簇頭傳遞至基站。因此，簇頭能耗需分情況討論。
情況1 le＞1時簇頭接收簇成員及鄰居簇頭數(shù)據(jù)包時的能耗分別為,。令c為鄰居簇頭的個數(shù)，滿足1≤c＜m。簇頭向鄰居簇頭發(fā)送數(shù)據(jù)包時的能耗為，其中 dCH為簇頭間的平均距離，滿足dCH= R / 2 = f （ kav）/2，其總能耗滿足 E=++。
情況 2 le = 1 時簇頭接收簇成員及鄰居簇頭數(shù)據(jù)包時的能耗同情況（1）。簇頭向基站發(fā)送數(shù)據(jù)包時的能耗為，其總能耗為?，F(xiàn)有文獻(xiàn)對簇頭到基站的平均距離估計值為 dBS=0.765?（L/2）[8]。下面對簇成員能耗進(jìn)行分析。
由于每個簇所占據(jù)的平均網(wǎng)絡(luò)面積大小為L2/m，該區(qū)域中節(jié)點(diǎn)的分布函數(shù)可表示為ρ=m / f（ x, y）[15]。假設(shè)簇頭位于簇中心，則簇成員與簇頭間的期望平方距離滿足
由式（13）可以看出網(wǎng)絡(luò)能耗與平均有效傳輸距離對應(yīng)的平均路徑損耗調(diào)整因子有關(guān)。
4 算法分析
4.1 算法實(shí)現(xiàn)
步驟 1 部署節(jié)點(diǎn)后，基站發(fā)送 InitialMSG，收到 InitialMSG的節(jié)點(diǎn)上報自身的位置、id等信息，基站獲取節(jié)點(diǎn)信息，統(tǒng)計節(jié)點(diǎn)總數(shù)，執(zhí)行WSIBTC算法。
步驟 2 基站根據(jù)0t將監(jiān)測區(qū)域分別進(jìn)行橫向、縱向上的劃分，形成多個子區(qū)域，每個子區(qū)域即是一個簇?；緩V播AdverinfoMSG告知節(jié)點(diǎn)所屬的簇。
步驟 3 簇內(nèi)節(jié)點(diǎn)以最大發(fā)射功率獲取鄰居節(jié)點(diǎn)信息表。根據(jù)節(jié)點(diǎn)的成簇穩(wěn)定性選取候選簇頭，最終簇頭的產(chǎn)生由候選簇頭在簇中的位置決定。最終簇頭產(chǎn)生后，簇內(nèi)形成星形拓?fù)浣Y(jié)構(gòu)。
步驟 4 簇成員暫時關(guān)閉通信模塊，進(jìn)入睡眠狀態(tài)。簇頭間交換鄰居信息表，計算自身與鄰居簇頭的權(quán)值，選擇鄰居簇頭。所有簇頭均執(zhí)行上述過程，簇頭間形成一種平面型拓?fù)浣Y(jié)構(gòu)。
步驟 5 拓?fù)浣Y(jié)構(gòu)形成后，基站喚醒簇成員，開始數(shù)據(jù)包的傳遞。當(dāng)完成一定的數(shù)據(jù)收集后，重新跳到步驟 3。循環(huán)執(zhí)行上述步驟，直到某個節(jié)點(diǎn)能量耗盡而失效。
4.2 消息復(fù)雜度
性質(zhì) 在所選網(wǎng)絡(luò)中，WSIBTC算法的消息復(fù)雜度為O（ N0）。
證明 如前所述，網(wǎng)絡(luò)中的簇頭個數(shù)為m，則簇成員的總數(shù)為 N0- m 。基站廣播AdverinfoMSG告知節(jié)點(diǎn)所屬的簇，并廣播一條網(wǎng)絡(luò)平均能量消息AVE_MSG給每一個節(jié)點(diǎn)，其次 N0T個候選簇頭共廣播 N0T條COMPETE_HEAD_MSG消息。每個候選簇頭廣播一條FINAL_HEAD_MSG消息宣布其競爭成功，或者廣播一條QUIT_MSG消息宣布其退出競爭。每個簇頭廣播一條 HEAD_MSG消息， N0- m 個簇成員廣播一條JOIN_MSG消息。構(gòu)建簇頭間拓?fù)浣Y(jié)構(gòu)時，每個簇頭需廣播HelloMSG消息獲取鄰居信息。因此，WSIBTC算法的消息開銷 滿 足 2 + N0T+ N0T+ m + （ N0- m ） + m =2N0T+N0+m+2，其消息復(fù)雜度為O（ N0）。 證畢
上述性質(zhì)說明WSIBTC算法的消息開銷較小，具有較好的能量效率。HEED算法[16]需在簇半徑內(nèi)進(jìn)行多次消息迭代，最多進(jìn)行Ntr×N次消息交換，其中 Ntr為消息迭代次數(shù)，通信開銷較大。WSIBTC算法避免了消息迭代，其通信開銷小于 HEED。EEUC的消息復(fù)雜度也為O（ N0），但其在選擇候選簇頭時沒有考慮節(jié)點(diǎn)的剩余能量，且競爭系數(shù)較小時，簇頭間的距離過大，增大了簇頭能耗。
4.3 網(wǎng)絡(luò)連通性
假設(shè)所有節(jié)點(diǎn)均以最大發(fā)射功率通信時構(gòu)建的全局拓?fù)錇镚 （V, E），執(zhí)行WSIBTC算法后得到的拓?fù)浣Y(jié)構(gòu)為 G*（ V, E*） 。
性質(zhì) 如果G （V, E） 是連通的，那么G*（V, E*）也是連通的。
證明 由于G（ V, E）連通，則G （V, E）中必然存在一條路徑 p t= （ w0= i , w1, w2, ???,wn-1,wn= j ） ，其中 wg和 wg+1（g = 0 ,1,2,???,n - 1 ） 互為鄰居節(jié)點(diǎn)。要證明 G*（ V, E*） 中節(jié)點(diǎn)i,j也是連通的，只需證明任意互為鄰居的節(jié)點(diǎn)對 wg和 wg+1之間存在通信路徑。WSIBTC算法中，G*（ V, E*）中各個節(jié)點(diǎn)均建立起自身的鄰居信息表，即如果節(jié)點(diǎn) wg和 wg+1互為鄰居節(jié)點(diǎn)，則一定存在彼此的鄰居信息表中，所以僅證明wg到 wg+1存在通信路徑即可。WSIBTC算法中需分兩種情況進(jìn)行討論：（1）節(jié)點(diǎn) wg到 wg+1存在單跳通信路徑；（2）節(jié)點(diǎn) wg到 wg+1存在多跳通信路徑，即節(jié)點(diǎn)和 wg+1為簇頭，且二者之間存在一個公共物理鄰居簇頭 ws，滿足 wg經(jīng) ws轉(zhuǎn)發(fā)到 wg+1比直接傳輸信息到 wg+1的權(quán)值更小。繼續(xù)分情況討論 wg和 ws之間以及 ws和 wg+1存在通信路徑即可。重復(fù)上述步驟，最終得到 wg和 wg+1連通的結(jié)論。由節(jié)點(diǎn)i,j的任意性可知，G*（ V, E*）中的每對節(jié)點(diǎn)之間都至少存在一條通信路徑，因此 G*（ V, E*） 連通。 證畢
4.4 生存函數(shù)的性質(zhì)
性質(zhì) 1 Si（0）=1。
因此， Si（ r）是單調(diào)遞減的。 證畢
5 仿真實(shí)現(xiàn)和分析
5.1 仿真參數(shù)設(shè)置
定義 6 從第1輪選擇簇頭開始到第1個節(jié)點(diǎn)死亡（能量消耗盡）的輪數(shù)，稱為網(wǎng)絡(luò)生存時間。
表 1 WSIBTC算法的各個參數(shù)仿真值
5.2 算法仿真結(jié)果分析
5.2.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 圖3為未經(jīng)拓?fù)淇刂茣r的網(wǎng)絡(luò)拓?fù)鋱D。從圖3中可以看出，節(jié)點(diǎn)以最大發(fā)射功率與可達(dá)鄰居節(jié)點(diǎn)相互通信，造成網(wǎng)絡(luò)中存在大量的冗余鏈路，節(jié)點(diǎn)能耗較大，網(wǎng)絡(luò)生存時間較短。圖4為執(zhí)行WSIBTC算法后得到的拓?fù)鋱D。從圖4中可以看出，監(jiān)測區(qū)域被劃分為9個子區(qū)域，即9個簇。黑色實(shí)心圓點(diǎn)為每個簇中選出的簇頭，黑色實(shí)線為簇頭間的拓?fù)潢P(guān)系，簇頭間形成了一種平面型的拓?fù)浣Y(jié)構(gòu)。通過圖 3，圖 4的對比可以看出由WSIBTC算法得到的拓?fù)浣Y(jié)構(gòu)精簡了節(jié)點(diǎn)間大量的冗余鏈路。簇頭間形成平面拓?fù)浣Y(jié)構(gòu)，當(dāng)某個中繼簇頭因外界原因突然失效時，簇頭間仍存在其他通信路徑。
圖3 未經(jīng)拓?fù)淇刂频木W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
圖5 無線信號不規(guī)則性對 網(wǎng)絡(luò)生存時間的影響
5.2.2 無線信號不規(guī)則性對網(wǎng)絡(luò)性能的影響 圖5為無線信號不規(guī)則性對網(wǎng)絡(luò)生存時間的影響，可以看出DOI較大時會縮短網(wǎng)絡(luò)的生存時間，降低節(jié)點(diǎn)平均有效傳輸距離。監(jiān)測區(qū)域需被劃分為更多的子區(qū)域以保證簇內(nèi)及簇間節(jié)點(diǎn)的通信，即每一輪擔(dān)任簇頭的節(jié)點(diǎn)數(shù)增多，需進(jìn)行處理及轉(zhuǎn)發(fā)的數(shù)據(jù)包的數(shù)量增大，使節(jié)點(diǎn)能耗速率增大，如圖6所示。存活節(jié)點(diǎn)的數(shù)量可以反映網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況。存活節(jié)點(diǎn)的數(shù)量越多，說明網(wǎng)絡(luò)能量利用率越高，節(jié)點(diǎn)壽命越長。圖6為DOI對網(wǎng)絡(luò)剩余能量的影響?？梢钥闯霎?dāng)DOI較大時，其能耗曲線相對較陡?；谏鲜鲈?，DOI較大時不僅會使網(wǎng)絡(luò)出現(xiàn)第1個死亡節(jié)點(diǎn)的時間提前，同時增大了網(wǎng)絡(luò)能耗速率。
5.2.3 網(wǎng)絡(luò)能耗對比 圖 7比較各算法的網(wǎng)絡(luò)生存時間。如圖7可知WSIBTC算法相比于其他幾種算法，有效地延長了網(wǎng)絡(luò)的生存時間。LEACH,MODELEACH, MODELEACHST與MODELEACHHT算法中簇頭與基站之間采用單跳通信方式，距離基站較遠(yuǎn)的簇頭能耗較大，網(wǎng)絡(luò)生存時間較短。在MODELEACH算法的基礎(chǔ)上通過分別引入一個軟門限與硬門限值降低簇頭重選頻率，使網(wǎng)絡(luò)生存時間得以延長，但是其依然保留了LEACH算法原有的拓?fù)浣Y(jié)構(gòu)。EEUC算法在選取候選簇頭時沒有考慮節(jié)點(diǎn)的剩余能量，且在競爭系數(shù)較小時會導(dǎo)致簇頭間距離過大，使簇頭能耗過大。WSIBTC算法可以避免網(wǎng)絡(luò)進(jìn)入瓶頸期后存在部分節(jié)點(diǎn)剩余能量較高的現(xiàn)象，簇頭在選擇鄰居簇頭時在一定程度上平衡了簇頭間的能耗，因此有效延長了網(wǎng)絡(luò)的生存時間。圖8比較各算法的網(wǎng)絡(luò)能耗。從圖8中可知其他幾種算法的網(wǎng)絡(luò)能耗速率均高于 WSIBTC算法，其原因與上述比較網(wǎng)絡(luò)生存時間的原因相同。
圖9比較各算法的網(wǎng)絡(luò)能量均衡性。從圖9中可知EEUC算法表現(xiàn)出了良好的能量均衡性，其在出現(xiàn)第 1 個死亡節(jié)點(diǎn)后，網(wǎng)絡(luò)即進(jìn)入衰亡期，大量節(jié)點(diǎn)隨之死亡，說明基于節(jié)點(diǎn)競爭半徑的非均勻分簇算法能夠有效地平衡節(jié)點(diǎn)間的能耗。MODELEACH,MODELEACHHT, MODELEAC HST算法存在節(jié)點(diǎn)能耗不均衡的現(xiàn)象。WSIBTC算法的網(wǎng)絡(luò)能量均衡性介于上述算法之間，且在考慮無線信號不規(guī)則性時，其網(wǎng)絡(luò)能量均衡性會受到影響。圖10比較各算法產(chǎn)生的有效數(shù)據(jù)包的數(shù)量。有效數(shù)據(jù)包的數(shù)量是指在未進(jìn)行數(shù)據(jù)融合時簇頭需向基站傳遞的數(shù)據(jù)包的數(shù)量。從圖10中可以才看出WSIBTC算法產(chǎn)生的有效數(shù)據(jù)包的數(shù)量高于其他幾種算法，并且接近于EEUC算法產(chǎn)生的有效數(shù)據(jù)包的數(shù)量。綜合來看，WSIBTC算法相比于其他幾種算法效果更優(yōu)。
圖6 無線信號不規(guī)則性對網(wǎng)絡(luò)能耗的影響
圖7 網(wǎng)絡(luò)生存時間比較圖
圖8 網(wǎng)絡(luò)能耗比較圖
圖9 網(wǎng)絡(luò)能量均衡性比較圖
圖10 網(wǎng)絡(luò)有效數(shù)據(jù)包的數(shù)量比較圖
6 結(jié)束語
本文從子區(qū)域個數(shù)的確定、候選簇頭的選取、最終簇頭的確定以及簇頭間拓?fù)浣Y(jié)構(gòu)的建立4個方面研究基于無線信號不規(guī)則性的無線傳感網(wǎng)層次型拓?fù)淇刂扑惴?。在WSIBTC算法中根據(jù)節(jié)點(diǎn)平均有效傳輸距離將監(jiān)測區(qū)域劃分為多個子區(qū)域，并根據(jù)RBD圖對節(jié)點(diǎn)的成簇穩(wěn)定性進(jìn)行建模，作為選取候選簇頭的標(biāo)準(zhǔn)，最終簇頭的確定則由候選簇頭在簇內(nèi)的位置決定。在建立簇頭間的拓?fù)浣Y(jié)構(gòu)時，根據(jù)粒子間的作用力定義了節(jié)點(diǎn)間的“粘度”函數(shù)，并在此基礎(chǔ)上定義了簇頭間的權(quán)值函數(shù)作為選擇鄰居簇頭的標(biāo)準(zhǔn)。分析了節(jié)點(diǎn)以及網(wǎng)絡(luò)能耗，并給出了網(wǎng)絡(luò)每一輪能耗的理論模型。在此基礎(chǔ)上，對算法的消息復(fù)雜度、網(wǎng)絡(luò)連通性以及節(jié)點(diǎn)生存函數(shù)的性質(zhì)進(jìn)行了分析證明。最后仿真比較無線信號不規(guī)則性對網(wǎng)絡(luò)生存時間、網(wǎng)絡(luò)能耗的影響以及 LEACH,EEUC, MODELEACH, MODELEACHST, MODE LEACHHT和WSIBTC算法的網(wǎng)絡(luò)生存時間、網(wǎng)絡(luò)能耗、網(wǎng)絡(luò)能量均衡性和網(wǎng)絡(luò)中產(chǎn)生的有效數(shù)據(jù)包的數(shù)量。
[1] 陳友榮, 周駿華, 尉理哲, 等. 基于網(wǎng)格的移動無線傳感網(wǎng)生存時間優(yōu)化算法[J]. 電子與信息學(xué)報, 2014, 36（10）:2370-2378.Chen You-rong, Zhou Jun-hua, Wei Li-zhe, et al.. Grid-based lifetime optimization algorithm for mobile wireless sensor networks[J]. Journal of Electronics & Information Technology,2014, 36 （10）: 2370-2378.
[2] Salarian H, Chin K W, and Naghdy F. An energy-efficient mobile-sink path selection strategy for wireless sensor networks[J]. IEEE Transactions on Vehicular Technology,2014, 63（5）: 2407-2419.
[3] Thakkar A and Kotecha K. Cluster head election for energy and delay constraint applications of wireless sensor networks[J]. IEEE Sensors Journal, 2014, 14（8）: 2658-2664.
[4] Heinzelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. IEEE Proceedings of the 33rd Annual Hawaii International Conference, Hawaii, 2000:8020-8029.
[5] Mahmood D, Javaid N, Mahmood S, et al.. A variant of LEACH for WSNs[C]. IEEE 2013 Eighth Internatioanal Conference on Broadband and Wireless Computing,Communication and Applications （BWCCA）, Compiegne,2013: 158-163.
[6] Sheikhpour R and Jabbehdari S. An energyefficient chainbased routing protocol for wireless sensor networks[J]. KSII Transactions on Internet and Information Systems, 2013,7（6）: 1357-1378.
[7] 李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計算機(jī)學(xué)報, 2007, 30（1）: 27-36.Li Cheng-fa, Chen Gui-hai, Ye Mao, et al.. An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Juornal of Computers, 2007, 30（1）: 27-36.
[8] 尚鳳軍, Mehran A, Tadeusz W. 無線傳感器網(wǎng)絡(luò)的分布式能量條有效非均勻成簇算法[J]. 通信學(xué)報, 2009, 30（10）: 34-43.Shang Feng-jun, Mehran A, and Tadeusz W. Distributed energy efficient unequal clustering algorithm for wireless sensor networks[J]. Journal on Communications, 2009, 30（10）:34-43.
[9] Kumar D. Performance analysis of energy efficient clustering protocols for maximising lifetime of wireless sensor networks[J]. IET Wireless Sensor Systems, 2014, 4（1）: 9-16.
[10] Jafri M R, Javaid N, Javaid A, et al.. Maximizing the lifetime of multi-chain pegasis using sink mobility[J]. World Applied Sciences Journal, 2013, 21（9）: 1283-1289.
[11] Zhou G, He T, Krishnamurthy S, et al.. Models and solutions for radio irregularity in wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2006, 2（2）: 221-262.
[12] 周祖德, 胡鵬, 李方敏. 無線傳感器網(wǎng)絡(luò)分簇通信協(xié)議的可靠性方案[J]. 通信學(xué)報, 2008, 29（5）: 114-121.Zhou Zu-de, Hu Peng, and Li Fang-min. Reliable scheme for the cluster-based communication protocol in wireless sensor networks[J]. Journal on Communications, 2008, 29（5）:114-121.
[13] Ammari H M. An energy-aware cover-sense-inform framework for k-covered wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23（4）:651-658.
[14] 郝曉辰, 竇晶晶, 劉彬. 基于路徑損耗的無線傳感器網(wǎng)絡(luò)分布式拓?fù)淇刂扑惴╗J]. 軟件學(xué)報, 2009, 20（12）: 3213-3222.Hao Xiao-chen, Dou Jing-jing, and Liu Bin. Path-loss based distributed topology control algorithm for wireless sensor networks[J]. Journal of Software, 2009, 20（12）: 3213-3222.
[15] 劉浩然, 韓濤, 李雅倩, 等. 具有路徑損耗優(yōu)化特性的 WSN無標(biāo)度容錯拓?fù)淇刂扑惴╗J]. 通信學(xué)報, 2014, 35（6）: 64-72.Liu Hao-ran, Han Tao, Li Ya-qian, et al.. Scale-free fault-tolerant topology control algorithm in wireless sensor network with optimization of path energy consumption[J].Journal on Communications, 2014, 35（6）: 64-72.
[16] Younis O and 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.
[17] 湯強(qiáng), 汪秉文, 戴志誠, 等. 半集中式能耗均衡多跳分簇協(xié)議[J]. 小型微型計算機(jī)系統(tǒng), 2010, 31（4）: 583-586.Tang Qiang, Wang Bing-wen, Dai Zhi-cheng, et al.. Semicentralized clustering protocol with energy balance and multi-hop transmission[J]. Journal of Chinese Computer Systems, 2010, 31（4）: 583-586.?
猜你喜歡
120t轉(zhuǎn)爐降低工序能耗生產(chǎn)實(shí)踐昆鋼科技(2022年2期)2022-07-08 06:36:14 能耗雙控下，漲價潮再度來襲！當(dāng)代水產(chǎn)(2021年10期)2022-01-12 06:20:28 探討如何設(shè)計零能耗住宅建材發(fā)展導(dǎo)向(2021年23期)2021-03-08 01:05:38 日本先進(jìn)的“零能耗住宅”華人時刊(2018年15期)2018-11-10 03:25:26 SmartSniff網(wǎng)絡(luò)安全和信息化(2018年4期)2018-11-09 12:01:54 可惡的“偽基站”探索科學(xué)(2017年4期)2017-05-04 04:09:47 基于GSM基站ID的高速公路路徑識別系統(tǒng)中國交通信息化(2016年8期)2016-06-06 03:56:25 小基站助力“提速降費(fèi)”移動通信(2015年17期)2015-08-24 08:13:10 基站輻射之爭亟待科學(xué)家發(fā)聲發(fā)明與創(chuàng)新(2015年29期)2015-02-27 10:39:43 基于Libpcap的網(wǎng)絡(luò)數(shù)據(jù)包捕獲器的設(shè)計與實(shí)現(xiàn)中國新通信(2014年11期)2014-09-11 19:27:52
唐 宏 王惠珠
1 引言
無線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks,WSNs）由大量能量受限的傳感器設(shè)備組成，延長網(wǎng)絡(luò)生存時間是目前首先需要考慮的問題[1,2]。拓?fù)淇刂剖且环N重要的節(jié)能技術(shù)，在保證覆蓋和連通質(zhì)量的條件下，通過減少冗余鏈路降低網(wǎng)絡(luò)能耗[3]。層次型拓?fù)淇刂扑惴ù蠖家訪EACH算法為基礎(chǔ)發(fā)展而來，其拓?fù)浣Y(jié)構(gòu)主要有3類：（1）簇內(nèi)單跳、簇間單跳[4,5]；（2）簇內(nèi)多跳、簇間多跳[6]；（3）單多跳相結(jié)合[7,8]。其中實(shí)現(xiàn)分簇的方法主要有靜態(tài)分簇[6,9]和動態(tài)分簇。選取簇頭的方式主要有4類：（1）采用隨機(jī)數(shù)閾值，使產(chǎn)生的隨機(jī)數(shù)小于該閾值的節(jié)點(diǎn)成為簇頭[4,5]。（2）考慮節(jié)點(diǎn)剩余能量，使剩余能量較高的節(jié)點(diǎn)優(yōu)先成為簇頭[8]。（3）考慮節(jié)點(diǎn)競爭半徑，使基站附近形成較小的簇，緩解基站附近的“熱區(qū)”問題[7,8]。（4）綜合考慮節(jié)點(diǎn)剩余能量以及到基站的距離，使剩余能量較高且距離基站較近的節(jié)點(diǎn)優(yōu)先成為簇頭[10]。
上述方法未考慮節(jié)點(diǎn)成為簇頭后簇結(jié)構(gòu)的性能，且未考慮無線信號不規(guī)則性對拓?fù)錁?gòu)建過程的影響。延長網(wǎng)絡(luò)生存時間的同時未兼顧網(wǎng)絡(luò)能量均衡性，且存在簇頭間鏈路較稀疏的情況。本文欲在考慮無線信號不規(guī)則性的條件下，對節(jié)點(diǎn)成為簇頭后的簇結(jié)構(gòu)穩(wěn)定性建模，并使簇頭間形成平面型數(shù)據(jù)轉(zhuǎn)發(fā)層，構(gòu)建兩層的WSNs拓?fù)浣Y(jié)構(gòu)。該方法首先根據(jù)無線信號不規(guī)則性 DOI（Degree Of Irregularity）模型[11]定義區(qū)域分割參數(shù)實(shí)現(xiàn)靜態(tài)分簇。其次，根據(jù)節(jié)點(diǎn)成簇穩(wěn)定性選取候選簇頭，并根據(jù)候選簇頭在簇內(nèi)的位置確定最終簇頭。簇頭間則形成平面型拓?fù)浣Y(jié)構(gòu)以避免由于中繼簇頭突然失效造成的網(wǎng)絡(luò)分割。最后給出WSIBTC算法與其他幾類算法的實(shí)驗比較結(jié)果。
2 系統(tǒng)假設(shè)和能耗模型
2.1 系統(tǒng)假設(shè)
（1）傳感器節(jié)點(diǎn)隨機(jī)分布于監(jiān)測區(qū)域內(nèi)，基站位于監(jiān)測區(qū)域之外；
（2）傳感器節(jié)點(diǎn)和基站部署完成后處于靜止?fàn)顟B(tài)，前者同構(gòu)，能量受限，后者能量無限；
（3）傳感器節(jié)點(diǎn)通過現(xiàn)有的定位技術(shù)或者接收信號強(qiáng)度與節(jié)點(diǎn)間距離的關(guān)系獲得自身在監(jiān)測區(qū)域內(nèi)的具體位置信息。
定義 1 WSNs可以抽象為2維平面圖G （V, E）。其中G為節(jié)點(diǎn)以最大發(fā)射功率相互通信時形成的原始拓?fù)浣Y(jié)構(gòu)，V為節(jié)點(diǎn)集合，E為節(jié)點(diǎn)間邊的集合。
定義 2 集合 VPH包含的元素為任意節(jié)點(diǎn)的物理鄰居節(jié)點(diǎn)。對于任意的節(jié)點(diǎn)i,j∈V，若滿足i∈且 j ∈，則表示節(jié)點(diǎn)i和j相互覆蓋；如果i∈且j?VPiH，則表示節(jié)點(diǎn)i覆蓋j，但是節(jié)點(diǎn)j不能覆蓋i。
定義 3 集合VL包含的元素為任意節(jié)點(diǎn)的邏輯鄰居節(jié)點(diǎn)。該集合是通過某種計算規(guī)則，將節(jié)點(diǎn)VPH集合中符合條件的物理鄰居節(jié)點(diǎn)篩選出來組成的節(jié)點(diǎn)集合。
定義5Ri為節(jié)點(diǎn)i的平均有效傳輸距離，Rj為節(jié)點(diǎn)j的平均有效傳輸距離， dij為節(jié)點(diǎn)i, j之間的距離，如果dij＜Ri且Rj，則i∈且j∈。
2.2 能耗模型
WSIBTC算法采用與LEACH算法相同的能耗模型。任意兩個可以相互通信且距離為d的節(jié)點(diǎn)間發(fā)送l比特數(shù)據(jù)的能耗為
其中 Ee表示發(fā)射端和接收端的電路損耗能量；d0為參考距離，滿足d0=。LEACH能耗模型定義如果 d ＜d0，功率放大損耗采用自由空間傳播模型；如果 d ≥d0，則采用多徑傳播模型。εfs和εmp分別表示兩種模型中對應(yīng)的功率放大器的放大參數(shù)。令DAE 為節(jié)點(diǎn)融合數(shù)據(jù)包時消耗的能量，則接收端接收l比特數(shù)據(jù)以及節(jié)點(diǎn)將接收到的0n個數(shù)據(jù)包融合為一個數(shù)據(jù)包時的能耗分別可用式（2），式（3）表示為
3 算法原理
3.1 子區(qū)域個數(shù)的確定
文獻(xiàn)[11]建立的無線信號不規(guī)則性數(shù)學(xué)模型為DOI模型，即由于傳感器設(shè)備本身的異構(gòu)性或者信號傳播時發(fā)生的衍射、反射等現(xiàn)象造成無線信號在不同傳播方向上具有不同的路徑損耗。DOI模型中節(jié)點(diǎn)各方向上的有效傳輸距離為
其中 Pt為節(jié)點(diǎn)發(fā)射功率；rss為接收端接收信號強(qiáng)度；Pl（d0）為自由空間傳播模型下的路徑損耗；α為路徑損耗指數(shù)，介于2～4之間。 ki為具體傳播方向上的路徑損耗調(diào)整因子，滿足其中DOI為傳播方向每改變1°時最大路徑損耗變化百分?jǐn)?shù)，介于0～0.02之間；Rand為服從韋伯分布的隨機(jī)數(shù)； i = 0 代表初始傳播方向。由于節(jié)點(diǎn)可以通過測量獲取接收信號強(qiáng)度，為了便于分析，將式（4）化簡為
令 Rmax表示節(jié)點(diǎn)最大有效傳輸距離， Rmin為最小有效傳輸距離，則節(jié)點(diǎn)平均有效傳輸距離為R = （Rmax+Rmin）/2。假設(shè)節(jié)點(diǎn)隨機(jī)分布于邊長為L的正方形區(qū)域中，子區(qū)域個數(shù)為m，則每個子區(qū)域的面積約為 L2/m。由正方形面積與對角線間的關(guān)系可得，子區(qū)域?qū)蔷€長度l0= L，則簇內(nèi)及相鄰子區(qū)域節(jié)點(diǎn)相互可達(dá)的條件為2l0≤R，因此m與R的關(guān)系需滿足 m ≥ 8L2/f2（kav）。其中 kav為R對應(yīng)的平均路徑損耗調(diào)整因子。綜上所述，區(qū)域分割參數(shù) t0需滿足
?表示向上取整?；靖鶕?jù)t0將監(jiān)測區(qū)域分別進(jìn)行橫向、縱向上的劃分，則 m =。
3.2 簇頭的確定
串聯(lián)與并聯(lián)模塊的組合可以描述任何復(fù)雜系統(tǒng)。在層次型網(wǎng)絡(luò)拓?fù)渲?，根?jù)節(jié)點(diǎn)感知到的數(shù)據(jù)間的依賴關(guān)系，其 RBD （Reliability Block Diagram）模型可以表示為[12]
圖1 有n個簇成員的簇頭RBD模型
節(jié)點(diǎn)i競爭簇頭時的成簇穩(wěn)定性可以表示為
其 中S（ r） 為 節(jié) 點(diǎn) 的 生 存 函 數(shù) ， 定 義 為Si（ r）=Ere（r）（r）。其中（r）為節(jié)點(diǎn)i第r輪的剩余能量，Ere（r）為第r輪網(wǎng)絡(luò)平均剩余能量。
候選簇頭的產(chǎn)生是形成簇結(jié)構(gòu)的基礎(chǔ)。子區(qū)域中的節(jié)點(diǎn)均產(chǎn)生一個0～1之間的隨機(jī)數(shù)，若節(jié)點(diǎn)i產(chǎn)生的隨機(jī)數(shù)小于等于閾值T（ i），則廣播其為候選簇頭的消息?，F(xiàn)有文獻(xiàn)對LEACH算法中T（ i）的改進(jìn)主要通過引入節(jié)點(diǎn)剩余能量以及全網(wǎng)平均剩余能量。當(dāng)網(wǎng)絡(luò)進(jìn)入瓶頸期，存活節(jié)點(diǎn)較低的能量等級使T（ i）大大減小，造成簇頭選取過程的不穩(wěn)定[9]。考慮上述因素，一種新的閾值計算公式可以表示為
其中p為節(jié)點(diǎn)成為簇頭的概率，r是目前循環(huán)進(jìn)行的輪數(shù)，0G為最近1/p輪中尚未成為簇頭的節(jié)點(diǎn)集合。產(chǎn)生的隨機(jī)數(shù)小于等于（）T i的簇成員將成為候選簇頭，廣播COMPETE_HEAD_MSG。
簇頭在簇中的位置直接影響著簇成員的能耗。假設(shè)每個簇中距離基站最近和最遠(yuǎn)的節(jié)點(diǎn)分別為i,j,ijd為節(jié)點(diǎn)i,j之間的距離。以ijd為直徑畫圓，候選簇頭y,h,g的位置如圖2所示。根據(jù)三角公式，位于該圓域內(nèi)且距離節(jié)點(diǎn)i,j最近的候選簇頭將優(yōu)先成為最終簇頭。
競選成功的候選簇頭廣播 FINAL_HEAD_MSG，接收到該消息的候選簇頭則廣播 QUIT_MSG宣布競爭失敗，成為簇成員。簇成員發(fā)送JOIN_MSG消息請求入簇，建立簇內(nèi)星型拓?fù)浣Y(jié)構(gòu)。
3.3 簇頭間權(quán)值函數(shù)的確定
圖2 候選簇頭位置示意圖
網(wǎng)絡(luò)中的節(jié)點(diǎn)可以被看作粒子，節(jié)點(diǎn)間的通信代價可以等效為粒子間的作用力[13]。WSIBTC算法將這種虛擬的作用力定義為節(jié)點(diǎn)間的“粘度”，其中簇頭的剩余能量等效為粒子的電荷量，簇頭間的路徑損耗作為簇頭通信時的代價，則簇頭間的“粘度”滿足
dBS為簇頭到基站的距離，γ1,γ2為加權(quán)系數(shù)，滿足γ1+γ2=1。
構(gòu)建簇頭間的拓?fù)浣Y(jié)構(gòu)時，簇成員暫時關(guān)閉通信模塊進(jìn)入睡眠狀態(tài)。簇頭廣播HelloMSG獲取鄰居信息表。簇頭i接收到鄰居簇頭j的信息表后，首先判斷是否存在公共物理鄰居簇頭s。若存在，則需比較W（ i, j） 與W（ i, s） + W （ s, j ） 的大小，判斷與物理鄰居進(jìn)行通信時的本地最小權(quán)值。令VLiS為簇頭i的單跳邏輯鄰居簇頭集合， VLiM為多跳邏輯鄰居簇頭集合，若存在公共物理鄰居簇頭s滿足W（ i, j）＞W(wǎng)（ i, s） + W （ s, j） ，則VLiM= VLiM∪ { j}且中繼簇頭為s，否則 VLiS
= VLiS∪{ j }。所有簇頭均執(zhí)行上述過程，建立平面型數(shù)據(jù)轉(zhuǎn)發(fā)層。
3.4 網(wǎng)絡(luò)能耗分析
假設(shè)監(jiān)測區(qū)域為邊長為L的正方形區(qū)域，節(jié)點(diǎn)數(shù)為 N0,n為子區(qū)域中節(jié)點(diǎn)個數(shù)，初始能量為 E0,m為子區(qū)域個數(shù)，每輪網(wǎng)絡(luò)能耗包括簇頭能耗 ECH和簇成員能耗 ECM。令網(wǎng)絡(luò)每輪能耗為 Erd，則 Erd=ECH+ECM。WSIBTC算法根據(jù)簇頭到基站的距離選取負(fù)責(zé)與基站直接通信的簇頭，其選擇依據(jù)為le=（dBS/ d0），其中 ? 為向上取整函數(shù)。若le＞1，即該簇頭與基站間的距離大于 d0，需通過中繼簇頭轉(zhuǎn)發(fā)數(shù)據(jù)；若le = 1 ，即該簇頭到基站的距離小于等于 d0。le = 1 的簇頭廣播自身的等級消息，其他簇頭則將相應(yīng)簇頭標(biāo)記為最終目的節(jié)點(diǎn)，使網(wǎng)絡(luò)中傳遞的數(shù)據(jù)包最終由該簇頭傳遞至基站。因此，簇頭能耗需分情況討論。
情況1 le＞1時簇頭接收簇成員及鄰居簇頭數(shù)據(jù)包時的能耗分別為,。令c為鄰居簇頭的個數(shù)，滿足1≤c＜m。簇頭向鄰居簇頭發(fā)送數(shù)據(jù)包時的能耗為，其中 dCH為簇頭間的平均距離，滿足dCH= R / 2 = f （ kav）/2，其總能耗滿足 E=++。
情況 2 le = 1 時簇頭接收簇成員及鄰居簇頭數(shù)據(jù)包時的能耗同情況（1）。簇頭向基站發(fā)送數(shù)據(jù)包時的能耗為，其總能耗為?，F(xiàn)有文獻(xiàn)對簇頭到基站的平均距離估計值為 dBS=0.765?（L/2）[8]。下面對簇成員能耗進(jìn)行分析。
由于每個簇所占據(jù)的平均網(wǎng)絡(luò)面積大小為L2/m，該區(qū)域中節(jié)點(diǎn)的分布函數(shù)可表示為ρ=m / f（ x, y）[15]。假設(shè)簇頭位于簇中心，則簇成員與簇頭間的期望平方距離滿足
由式（13）可以看出網(wǎng)絡(luò)能耗與平均有效傳輸距離對應(yīng)的平均路徑損耗調(diào)整因子有關(guān)。
4 算法分析
4.1 算法實(shí)現(xiàn)
步驟 1 部署節(jié)點(diǎn)后，基站發(fā)送 InitialMSG，收到 InitialMSG的節(jié)點(diǎn)上報自身的位置、id等信息，基站獲取節(jié)點(diǎn)信息，統(tǒng)計節(jié)點(diǎn)總數(shù)，執(zhí)行WSIBTC算法。
步驟 2 基站根據(jù)0t將監(jiān)測區(qū)域分別進(jìn)行橫向、縱向上的劃分，形成多個子區(qū)域，每個子區(qū)域即是一個簇?；緩V播AdverinfoMSG告知節(jié)點(diǎn)所屬的簇。
步驟 3 簇內(nèi)節(jié)點(diǎn)以最大發(fā)射功率獲取鄰居節(jié)點(diǎn)信息表。根據(jù)節(jié)點(diǎn)的成簇穩(wěn)定性選取候選簇頭，最終簇頭的產(chǎn)生由候選簇頭在簇中的位置決定。最終簇頭產(chǎn)生后，簇內(nèi)形成星形拓?fù)浣Y(jié)構(gòu)。
步驟 4 簇成員暫時關(guān)閉通信模塊，進(jìn)入睡眠狀態(tài)。簇頭間交換鄰居信息表，計算自身與鄰居簇頭的權(quán)值，選擇鄰居簇頭。所有簇頭均執(zhí)行上述過程，簇頭間形成一種平面型拓?fù)浣Y(jié)構(gòu)。
步驟 5 拓?fù)浣Y(jié)構(gòu)形成后，基站喚醒簇成員，開始數(shù)據(jù)包的傳遞。當(dāng)完成一定的數(shù)據(jù)收集后，重新跳到步驟 3。循環(huán)執(zhí)行上述步驟，直到某個節(jié)點(diǎn)能量耗盡而失效。
4.2 消息復(fù)雜度
性質(zhì) 在所選網(wǎng)絡(luò)中，WSIBTC算法的消息復(fù)雜度為O（ N0）。
證明 如前所述，網(wǎng)絡(luò)中的簇頭個數(shù)為m，則簇成員的總數(shù)為 N0- m 。基站廣播AdverinfoMSG告知節(jié)點(diǎn)所屬的簇，并廣播一條網(wǎng)絡(luò)平均能量消息AVE_MSG給每一個節(jié)點(diǎn)，其次 N0T個候選簇頭共廣播 N0T條COMPETE_HEAD_MSG消息。每個候選簇頭廣播一條FINAL_HEAD_MSG消息宣布其競爭成功，或者廣播一條QUIT_MSG消息宣布其退出競爭。每個簇頭廣播一條 HEAD_MSG消息， N0- m 個簇成員廣播一條JOIN_MSG消息。構(gòu)建簇頭間拓?fù)浣Y(jié)構(gòu)時，每個簇頭需廣播HelloMSG消息獲取鄰居信息。因此，WSIBTC算法的消息開銷 滿 足 2 + N0T+ N0T+ m + （ N0- m ） + m =2N0T+N0+m+2，其消息復(fù)雜度為O（ N0）。 證畢
上述性質(zhì)說明WSIBTC算法的消息開銷較小，具有較好的能量效率。HEED算法[16]需在簇半徑內(nèi)進(jìn)行多次消息迭代，最多進(jìn)行Ntr×N次消息交換，其中 Ntr為消息迭代次數(shù)，通信開銷較大。WSIBTC算法避免了消息迭代，其通信開銷小于 HEED。EEUC的消息復(fù)雜度也為O（ N0），但其在選擇候選簇頭時沒有考慮節(jié)點(diǎn)的剩余能量，且競爭系數(shù)較小時，簇頭間的距離過大，增大了簇頭能耗。
4.3 網(wǎng)絡(luò)連通性
假設(shè)所有節(jié)點(diǎn)均以最大發(fā)射功率通信時構(gòu)建的全局拓?fù)錇镚 （V, E），執(zhí)行WSIBTC算法后得到的拓?fù)浣Y(jié)構(gòu)為 G*（ V, E*） 。
性質(zhì) 如果G （V, E） 是連通的，那么G*（V, E*）也是連通的。
證明 由于G（ V, E）連通，則G （V, E）中必然存在一條路徑 p t= （ w0= i , w1, w2, ???,wn-1,wn= j ） ，其中 wg和 wg+1（g = 0 ,1,2,???,n - 1 ） 互為鄰居節(jié)點(diǎn)。要證明 G*（ V, E*） 中節(jié)點(diǎn)i,j也是連通的，只需證明任意互為鄰居的節(jié)點(diǎn)對 wg和 wg+1之間存在通信路徑。WSIBTC算法中，G*（ V, E*）中各個節(jié)點(diǎn)均建立起自身的鄰居信息表，即如果節(jié)點(diǎn) wg和 wg+1互為鄰居節(jié)點(diǎn)，則一定存在彼此的鄰居信息表中，所以僅證明wg到 wg+1存在通信路徑即可。WSIBTC算法中需分兩種情況進(jìn)行討論：（1）節(jié)點(diǎn) wg到 wg+1存在單跳通信路徑；（2）節(jié)點(diǎn) wg到 wg+1存在多跳通信路徑，即節(jié)點(diǎn)和 wg+1為簇頭，且二者之間存在一個公共物理鄰居簇頭 ws，滿足 wg經(jīng) ws轉(zhuǎn)發(fā)到 wg+1比直接傳輸信息到 wg+1的權(quán)值更小。繼續(xù)分情況討論 wg和 ws之間以及 ws和 wg+1存在通信路徑即可。重復(fù)上述步驟，最終得到 wg和 wg+1連通的結(jié)論。由節(jié)點(diǎn)i,j的任意性可知，G*（ V, E*）中的每對節(jié)點(diǎn)之間都至少存在一條通信路徑，因此 G*（ V, E*） 連通。 證畢
4.4 生存函數(shù)的性質(zhì)
性質(zhì) 1 Si（0）=1。
因此， Si（ r）是單調(diào)遞減的。 證畢
5 仿真實(shí)現(xiàn)和分析
5.1 仿真參數(shù)設(shè)置
定義 6 從第1輪選擇簇頭開始到第1個節(jié)點(diǎn)死亡（能量消耗盡）的輪數(shù)，稱為網(wǎng)絡(luò)生存時間。
表 1 WSIBTC算法的各個參數(shù)仿真值
5.2 算法仿真結(jié)果分析
5.2.1 網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu) 圖3為未經(jīng)拓?fù)淇刂茣r的網(wǎng)絡(luò)拓?fù)鋱D。從圖3中可以看出，節(jié)點(diǎn)以最大發(fā)射功率與可達(dá)鄰居節(jié)點(diǎn)相互通信，造成網(wǎng)絡(luò)中存在大量的冗余鏈路，節(jié)點(diǎn)能耗較大，網(wǎng)絡(luò)生存時間較短。圖4為執(zhí)行WSIBTC算法后得到的拓?fù)鋱D。從圖4中可以看出，監(jiān)測區(qū)域被劃分為9個子區(qū)域，即9個簇。黑色實(shí)心圓點(diǎn)為每個簇中選出的簇頭，黑色實(shí)線為簇頭間的拓?fù)潢P(guān)系，簇頭間形成了一種平面型的拓?fù)浣Y(jié)構(gòu)。通過圖 3，圖 4的對比可以看出由WSIBTC算法得到的拓?fù)浣Y(jié)構(gòu)精簡了節(jié)點(diǎn)間大量的冗余鏈路。簇頭間形成平面拓?fù)浣Y(jié)構(gòu)，當(dāng)某個中繼簇頭因外界原因突然失效時，簇頭間仍存在其他通信路徑。
圖3 未經(jīng)拓?fù)淇刂频木W(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)
圖5 無線信號不規(guī)則性對 網(wǎng)絡(luò)生存時間的影響
5.2.2 無線信號不規(guī)則性對網(wǎng)絡(luò)性能的影響 圖5為無線信號不規(guī)則性對網(wǎng)絡(luò)生存時間的影響，可以看出DOI較大時會縮短網(wǎng)絡(luò)的生存時間，降低節(jié)點(diǎn)平均有效傳輸距離。監(jiān)測區(qū)域需被劃分為更多的子區(qū)域以保證簇內(nèi)及簇間節(jié)點(diǎn)的通信，即每一輪擔(dān)任簇頭的節(jié)點(diǎn)數(shù)增多，需進(jìn)行處理及轉(zhuǎn)發(fā)的數(shù)據(jù)包的數(shù)量增大，使節(jié)點(diǎn)能耗速率增大，如圖6所示。存活節(jié)點(diǎn)的數(shù)量可以反映網(wǎng)絡(luò)中節(jié)點(diǎn)的能量均衡情況。存活節(jié)點(diǎn)的數(shù)量越多，說明網(wǎng)絡(luò)能量利用率越高，節(jié)點(diǎn)壽命越長。圖6為DOI對網(wǎng)絡(luò)剩余能量的影響?？梢钥闯霎?dāng)DOI較大時，其能耗曲線相對較陡?；谏鲜鲈?，DOI較大時不僅會使網(wǎng)絡(luò)出現(xiàn)第1個死亡節(jié)點(diǎn)的時間提前，同時增大了網(wǎng)絡(luò)能耗速率。
5.2.3 網(wǎng)絡(luò)能耗對比 圖 7比較各算法的網(wǎng)絡(luò)生存時間。如圖7可知WSIBTC算法相比于其他幾種算法，有效地延長了網(wǎng)絡(luò)的生存時間。LEACH,MODELEACH, MODELEACHST與MODELEACHHT算法中簇頭與基站之間采用單跳通信方式，距離基站較遠(yuǎn)的簇頭能耗較大，網(wǎng)絡(luò)生存時間較短。在MODELEACH算法的基礎(chǔ)上通過分別引入一個軟門限與硬門限值降低簇頭重選頻率，使網(wǎng)絡(luò)生存時間得以延長，但是其依然保留了LEACH算法原有的拓?fù)浣Y(jié)構(gòu)。EEUC算法在選取候選簇頭時沒有考慮節(jié)點(diǎn)的剩余能量，且在競爭系數(shù)較小時會導(dǎo)致簇頭間距離過大，使簇頭能耗過大。WSIBTC算法可以避免網(wǎng)絡(luò)進(jìn)入瓶頸期后存在部分節(jié)點(diǎn)剩余能量較高的現(xiàn)象，簇頭在選擇鄰居簇頭時在一定程度上平衡了簇頭間的能耗，因此有效延長了網(wǎng)絡(luò)的生存時間。圖8比較各算法的網(wǎng)絡(luò)能耗。從圖8中可知其他幾種算法的網(wǎng)絡(luò)能耗速率均高于 WSIBTC算法，其原因與上述比較網(wǎng)絡(luò)生存時間的原因相同。
圖9比較各算法的網(wǎng)絡(luò)能量均衡性。從圖9中可知EEUC算法表現(xiàn)出了良好的能量均衡性，其在出現(xiàn)第 1 個死亡節(jié)點(diǎn)后，網(wǎng)絡(luò)即進(jìn)入衰亡期，大量節(jié)點(diǎn)隨之死亡，說明基于節(jié)點(diǎn)競爭半徑的非均勻分簇算法能夠有效地平衡節(jié)點(diǎn)間的能耗。MODELEACH,MODELEACHHT, MODELEAC HST算法存在節(jié)點(diǎn)能耗不均衡的現(xiàn)象。WSIBTC算法的網(wǎng)絡(luò)能量均衡性介于上述算法之間，且在考慮無線信號不規(guī)則性時，其網(wǎng)絡(luò)能量均衡性會受到影響。圖10比較各算法產(chǎn)生的有效數(shù)據(jù)包的數(shù)量。有效數(shù)據(jù)包的數(shù)量是指在未進(jìn)行數(shù)據(jù)融合時簇頭需向基站傳遞的數(shù)據(jù)包的數(shù)量。從圖10中可以才看出WSIBTC算法產(chǎn)生的有效數(shù)據(jù)包的數(shù)量高于其他幾種算法，并且接近于EEUC算法產(chǎn)生的有效數(shù)據(jù)包的數(shù)量。綜合來看，WSIBTC算法相比于其他幾種算法效果更優(yōu)。
圖6 無線信號不規(guī)則性對網(wǎng)絡(luò)能耗的影響
圖7 網(wǎng)絡(luò)生存時間比較圖
圖8 網(wǎng)絡(luò)能耗比較圖
圖9 網(wǎng)絡(luò)能量均衡性比較圖
圖10 網(wǎng)絡(luò)有效數(shù)據(jù)包的數(shù)量比較圖
6 結(jié)束語
本文從子區(qū)域個數(shù)的確定、候選簇頭的選取、最終簇頭的確定以及簇頭間拓?fù)浣Y(jié)構(gòu)的建立4個方面研究基于無線信號不規(guī)則性的無線傳感網(wǎng)層次型拓?fù)淇刂扑惴?。在WSIBTC算法中根據(jù)節(jié)點(diǎn)平均有效傳輸距離將監(jiān)測區(qū)域劃分為多個子區(qū)域，并根據(jù)RBD圖對節(jié)點(diǎn)的成簇穩(wěn)定性進(jìn)行建模，作為選取候選簇頭的標(biāo)準(zhǔn)，最終簇頭的確定則由候選簇頭在簇內(nèi)的位置決定。在建立簇頭間的拓?fù)浣Y(jié)構(gòu)時，根據(jù)粒子間的作用力定義了節(jié)點(diǎn)間的“粘度”函數(shù)，并在此基礎(chǔ)上定義了簇頭間的權(quán)值函數(shù)作為選擇鄰居簇頭的標(biāo)準(zhǔn)。分析了節(jié)點(diǎn)以及網(wǎng)絡(luò)能耗，并給出了網(wǎng)絡(luò)每一輪能耗的理論模型。在此基礎(chǔ)上，對算法的消息復(fù)雜度、網(wǎng)絡(luò)連通性以及節(jié)點(diǎn)生存函數(shù)的性質(zhì)進(jìn)行了分析證明。最后仿真比較無線信號不規(guī)則性對網(wǎng)絡(luò)生存時間、網(wǎng)絡(luò)能耗的影響以及 LEACH,EEUC, MODELEACH, MODELEACHST, MODE LEACHHT和WSIBTC算法的網(wǎng)絡(luò)生存時間、網(wǎng)絡(luò)能耗、網(wǎng)絡(luò)能量均衡性和網(wǎng)絡(luò)中產(chǎn)生的有效數(shù)據(jù)包的數(shù)量。
[1] 陳友榮, 周駿華, 尉理哲, 等. 基于網(wǎng)格的移動無線傳感網(wǎng)生存時間優(yōu)化算法[J]. 電子與信息學(xué)報, 2014, 36（10）:2370-2378.Chen You-rong, Zhou Jun-hua, Wei Li-zhe, et al.. Grid-based lifetime optimization algorithm for mobile wireless sensor networks[J]. Journal of Electronics & Information Technology,2014, 36 （10）: 2370-2378.
[2] Salarian H, Chin K W, and Naghdy F. An energy-efficient mobile-sink path selection strategy for wireless sensor networks[J]. IEEE Transactions on Vehicular Technology,2014, 63（5）: 2407-2419.
[3] Thakkar A and Kotecha K. Cluster head election for energy and delay constraint applications of wireless sensor networks[J]. IEEE Sensors Journal, 2014, 14（8）: 2658-2664.
[4] Heinzelman W R, Chandrakasan A, and Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks[C]. IEEE Proceedings of the 33rd Annual Hawaii International Conference, Hawaii, 2000:8020-8029.
[5] Mahmood D, Javaid N, Mahmood S, et al.. A variant of LEACH for WSNs[C]. IEEE 2013 Eighth Internatioanal Conference on Broadband and Wireless Computing,Communication and Applications （BWCCA）, Compiegne,2013: 158-163.
[6] Sheikhpour R and Jabbehdari S. An energyefficient chainbased routing protocol for wireless sensor networks[J]. KSII Transactions on Internet and Information Systems, 2013,7（6）: 1357-1378.
[7] 李成法, 陳貴海, 葉懋, 等. 一種基于非均勻分簇的無線傳感器網(wǎng)絡(luò)路由協(xié)議[J]. 計算機(jī)學(xué)報, 2007, 30（1）: 27-36.Li Cheng-fa, Chen Gui-hai, Ye Mao, et al.. An uneven cluster-based routing protocol for wireless sensor networks[J].Chinese Juornal of Computers, 2007, 30（1）: 27-36.
[8] 尚鳳軍, Mehran A, Tadeusz W. 無線傳感器網(wǎng)絡(luò)的分布式能量條有效非均勻成簇算法[J]. 通信學(xué)報, 2009, 30（10）: 34-43.Shang Feng-jun, Mehran A, and Tadeusz W. Distributed energy efficient unequal clustering algorithm for wireless sensor networks[J]. Journal on Communications, 2009, 30（10）:34-43.
[9] Kumar D. Performance analysis of energy efficient clustering protocols for maximising lifetime of wireless sensor networks[J]. IET Wireless Sensor Systems, 2014, 4（1）: 9-16.
[10] Jafri M R, Javaid N, Javaid A, et al.. Maximizing the lifetime of multi-chain pegasis using sink mobility[J]. World Applied Sciences Journal, 2013, 21（9）: 1283-1289.
[11] Zhou G, He T, Krishnamurthy S, et al.. Models and solutions for radio irregularity in wireless sensor networks[J]. ACM Transactions on Sensor Networks, 2006, 2（2）: 221-262.
[12] 周祖德, 胡鵬, 李方敏. 無線傳感器網(wǎng)絡(luò)分簇通信協(xié)議的可靠性方案[J]. 通信學(xué)報, 2008, 29（5）: 114-121.Zhou Zu-de, Hu Peng, and Li Fang-min. Reliable scheme for the cluster-based communication protocol in wireless sensor networks[J]. Journal on Communications, 2008, 29（5）:114-121.
[13] Ammari H M. An energy-aware cover-sense-inform framework for k-covered wireless sensor networks[J]. IEEE Transactions on Parallel and Distributed Systems, 2012, 23（4）:651-658.
[14] 郝曉辰, 竇晶晶, 劉彬. 基于路徑損耗的無線傳感器網(wǎng)絡(luò)分布式拓?fù)淇刂扑惴╗J]. 軟件學(xué)報, 2009, 20（12）: 3213-3222.Hao Xiao-chen, Dou Jing-jing, and Liu Bin. Path-loss based distributed topology control algorithm for wireless sensor networks[J]. Journal of Software, 2009, 20（12）: 3213-3222.
[15] 劉浩然, 韓濤, 李雅倩, 等. 具有路徑損耗優(yōu)化特性的 WSN無標(biāo)度容錯拓?fù)淇刂扑惴╗J]. 通信學(xué)報, 2014, 35（6）: 64-72.Liu Hao-ran, Han Tao, Li Ya-qian, et al.. Scale-free fault-tolerant topology control algorithm in wireless sensor network with optimization of path energy consumption[J].Journal on Communications, 2014, 35（6）: 64-72.
[16] Younis O and 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.
[17] 湯強(qiáng), 汪秉文, 戴志誠, 等. 半集中式能耗均衡多跳分簇協(xié)議[J]. 小型微型計算機(jī)系統(tǒng), 2010, 31（4）: 583-586.Tang Qiang, Wang Bing-wen, Dai Zhi-cheng, et al.. Semicentralized clustering protocol with energy balance and multi-hop transmission[J]. Journal of Chinese Computer Systems, 2010, 31（4）: 583-586.?
猜你喜歡
昆鋼科技(2022年2期)2022-07-08 06:36:14
當(dāng)代水產(chǎn)(2021年10期)2022-01-12 06:20:28
建材發(fā)展導(dǎo)向(2021年23期)2021-03-08 01:05:38
華人時刊(2018年15期)2018-11-10 03:25:26
網(wǎng)絡(luò)安全和信息化(2018年4期)2018-11-09 12:01:54
探索科學(xué)(2017年4期)2017-05-04 04:09:47
中國交通信息化(2016年8期)2016-06-06 03:56:25
移動通信(2015年17期)2015-08-24 08:13:10
發(fā)明與創(chuàng)新(2015年29期)2015-02-27 10:39:43
中國新通信(2014年11期)2014-09-11 19:27:52
