基于節(jié)點度和通信代價的雙簇首交替算法*

2015-07-10 13:47:17許曉天李德敏東華大學信息科學與技術學院上海201620數字化紡織服裝技術教育部工程研究中心上海201620

通信技術 2015年2期

許曉天,李德敏,紫羅,周凡(1.東華大學信息科學與技術學院,上海201620;2.數字化紡織服裝技術教育部工程研究中心,上海201620)

許曉天1,2,李德敏1,2,紫羅1,2,周凡1,2
(1.東華大學信息科學與技術學院,上海201620;2.數字化紡織服裝技術教育部工程研究中心,上海201620)

本文提出一種基于節(jié)點度和通信代價的雙簇首交替算法——NDCC算法。該算法用于解決語音導游系統(tǒng)中靠近導游機的節(jié)點過度利用的問題,算法在移動自組織網絡中引入雙簇首輪換制度。該制度以優(yōu)先級為考查標準,綜合多種因素:以節(jié)點度的變化作為簇首交替的參考標準;計算雙簇首與簇內某個隨機節(jié)點的通信代價。最后,本文將NDCC算法在Matlab平臺進行多方面仿真,證明算法的優(yōu)勢,也提出本算法值得改進的方向。

雙簇首交替節(jié)點度通信代價

0 引言

在語音導游系統(tǒng)網絡中,通過利用節(jié)能算法文獻[1-2]可以實現均衡網絡能量的效果。但是在實際應用中,可能會出現距離導游機較近的節(jié)點在剩余能量較低的時候被選擇擔任簇首,這樣會造成節(jié)點因為能耗負擔過重而過早離開網絡,這不僅會對這個游客造成影響,一定程度上也會造成網絡分割從而對其他游客也造成影響。為解決這一問題,本文提出了Node Degree and Communication Costs(NDCC)算法,算法通過雙簇首的交替工作來調節(jié)能耗,以平衡網絡開銷,進而達到能量均衡的目的。

1 相關工作

2008年Chen等人在MANET分簇中,引入簇首備份的概念,提出BH-3hBAC分簇算法[3],該算法,通過評估機制選取備份簇首,減小簇首因為故障失效帶來的損失,提高簇的穩(wěn)定性。但是在網絡穩(wěn)定的情況下,備選簇首基本不會擔任簇首角色。

2010年Ebadi S等人提出了一種雙簇首機制[4],一個簇首負責接收簇內節(jié)點的數據、進行數據融合、將融合后的數據以及來自上層的數據進行轉發(fā);另一個簇頭負責將來自下層的數據向上層轉發(fā);該算法雖然可以減輕簇首節(jié)點的負擔,但兩個簇頭均需要在工作過程中保持偵聽狀態(tài),也會耗費大量的能量。

2012年Zhao等人提出了一種基于雙簇首交替和壓縮感知的路由協(xié)議DCHACS[5],協(xié)議采用分布式算法選舉臨時簇首,臨時簇首采用鄰居簇優(yōu)化算法動態(tài)調整各個簇的大小,然后利用局部信息重新選舉較優(yōu)的簇首;在數據傳輸階段,采用雙簇首交替機制分擔簇首的負擔,簇首節(jié)點利用壓縮感知理論進行數據融合,并進行簇間路由。但是算法的應用受到限制,不適用于移動自組織網絡。本文結合移動自組織網絡拓撲動態(tài)變化的特點進行算法設計。

文獻[6]提出了一種能量有效的加權分簇算法,該算法利用通信代價的思想,設計出通信代價主要由簇首與普通節(jié)點的距離相關的算法。本文算法增加了節(jié)點的剩余能量作為參考標準,將會提高算法的精確度。

本文的貢獻:在移動自組織網絡中引入雙簇首輪換制度,該制度以優(yōu)先級為考查標準,綜合多種因素:①考慮節(jié)點隨機移動對簇首的影響,以節(jié)點度的變化作為進行簇首交替的參考;②計算雙簇首與簇內某個隨機節(jié)點的通信代價,并且在文獻[6]的基礎上進行改進。詳見本文3.1、3.2章節(jié)。

2 準備工作

2.1 節(jié)點度的概念

如圖所示假設節(jié)點,A為簇首節(jié)點,以A為原點,在它的通信范圍內的鄰居節(jié)點個數定位節(jié)點度[7],表示為Dn。

圖1 節(jié)點度的概念Fig.1 Concept of node degrees

2.2 剩余能量計算

本文采用典型能量模型[8],傳輸K bit能量到達距離為d的位置,發(fā)送端所需要損耗的能量E(k,d)為

接收端能量消耗ER(k)為

Eelec表示發(fā)射電路消耗的能量,εfs表示當傳輸距離小于d0時,功率放大所需要的能量,εmp表示當傳輸距離大于等于d0時功率放大所需要的能量。

當普通節(jié)點接收到當前簇首節(jié)點的信息時,根據傳輸能量可以計算出剩余能量所處區(qū)間,當前能量為輪換次數。

3 主要工作

當簇形成以后,根據BH-3hBAC算法選出備選簇首。由于語音導游系統(tǒng)組成的網絡中節(jié)點的移動動態(tài)變化且隨機的,經過多次實驗研究論證,簇首與備選簇首的交替時間間隔定為10秒,在每一個時間段計算兩個簇首是否輪換。

3.1 基于通信代價的能耗估計

對于兩個簇首來講,啟動簇首輪換機制時,是否擔任簇首的優(yōu)先級主要由簇首節(jié)點度和通信代價來定,文獻[6]提出的通信代價公式由節(jié)點之間距離決定公式結果,本文改進后的通信代價的計算方法為:

其中cost(Ai,Hj)為節(jié)i與j的通信代價,d(Ai,Hj)為普通節(jié)點Ai與簇首節(jié)點Hj之間的距離,Ri為節(jié)點i的通信半徑,ET(Ai)-ET(Hj)為普通節(jié)點Ai與簇首節(jié)點Hj當前能量的絕對差值,Dall為整個網絡的直徑?？梢娡ㄐ糯鷥r不僅與節(jié)點之間的距離有關也與節(jié)點的剩余能量有關。

3.2 基于節(jié)點度和節(jié)點通信代價的分簇優(yōu)化算法假設某一時刻簇首的節(jié)點度為DH1,備選簇首的節(jié)點度為DH2。擔任簇首的優(yōu)先級P(Ai,Hj)計算方法為:

(Ai代表簇內普通節(jié)點,j為1或2)

在簇首競爭的時候比較兩個簇首的優(yōu)先級,即P(i,1)與P(i,2)的大小,選取優(yōu)先級高的節(jié)點為簇首。

3.3 算法描述

根據前面的理論基礎,基于節(jié)點度和節(jié)點通信代價的雙簇首交替算法——NDCC算法的描述如下:

Step1網絡部署完畢,所有節(jié)點進入工作狀態(tài)。

Step2若是網絡首輪啟動,導游節(jié)點向所有節(jié)點廣播網絡初始化消息;若是非首輪啟動,導游節(jié)點向全局發(fā)送消息喚醒所有節(jié)點,節(jié)點進入準備狀態(tài)。

Step3首輪計算采用BH-3hBAC算法,動態(tài)選出備選簇首。

Step4啟動簇首輪換機制,測算簇首和備選簇首的節(jié)點度。

Step5計算簇首和備選簇首對于某一隨機節(jié)點的通信代價。

Step6根據優(yōu)先級公式進行簇首輪換。

Step7網絡運行進入相對穩(wěn)定階段。當節(jié)點分布變化之后,轉到步驟3,網絡循環(huán)進行。

4 仿真

在Matlab平臺上對本文的NDCC算法與BH-3hBAC、文獻[6]算法多個方面進行模擬仿真。假設節(jié)點隨機分布在(x=0,y=0)和(x=100,y=100)的正方形區(qū)域內,信源源節(jié)點位于(x=50,y=50)的位置。信道的帶寬為1 Mbps,數據包大小為500 bit,能量模型如表1。其中εfs表示當傳輸距離小于d0時,功率放大所需要的能量,εmp表示當傳輸距離大于等于d0時功率放大所需要的能量。

表1 能量模型參數Table 1 Parameters of energymodel

實驗結果與分析

圖2 網絡平均剩余能量Fig.2 Average residual energy of the network

圖2 可以看出,隨著輪換次數的遞增,相對其他兩種算法,NDCC算法作用下的網絡平均剩余能量相對要高,但是由于算法復雜度較高或者其他原因導致在某些時刻剩余能量曲線低于BH-3hBAC算法。

圖3所示的是三種算法在不同節(jié)點密度下的網絡簇平均生存時間的對比,NDCC算法優(yōu)于其他兩種算法,可見算法起到了均衡節(jié)點能量的作用。

圖3 簇平均生存時間Fig.3 Average survival time of cluster

5 結語

本文提出一種基于節(jié)點度和通信代價的雙簇首交替算法——NDCC算法,在移動自組織網絡中引入雙簇首輪換制度。該制度以雙簇首節(jié)點的優(yōu)先級為主要參考標準,綜合節(jié)點度和通信代價等因素,進行雙簇首輪換。最后,通過在Matlab平臺對NDCC算法、BH-3hBAC算法、和文獻[6]進行多方面仿真比較,可以看出算法在均衡簇內節(jié)點的能量時起到了積極的作用;但是由于算法復雜度較高,網絡平均剩余能量的比較中顯示本文算法還有需要改進的地方;下一步工作中,可以在減少復雜度的方面對算法進行改進。

[1] ZOU Jian,LIDe-min,ZHANG Min.An Energy-Balanced Routing Algorithm for ZigBee Audio Guide System in Ad Hoc Social Network[C]//Information Technology for Manufacturing Systems.Qingdao:Advanced Engineering Forum,2012:1177-1182.

[2] 張躍,周杰.基于分簇的無線傳感器網絡通信協(xié)議LEACH研究[J].通信技術,2013(12):23-28. ZHANG Yue,ZHOU Jie.LEACH based on Clustering Communication Protocol for Wireless Sensor Networks [J].Communications Technology,2013(12):23-28.

[3] 陳嘉寧,謝高崗,張大方,曾彬.BH-3hBAC:一種穩(wěn)定的MANET分簇策略[J].系統(tǒng)仿真學報,2008,20 (6):1523-1528. CHEN Jia-ning,XIE Gao-gang,ZHANG Dafang, ZENG Bin.BH-3hBAC:A Stable Clustering Scheme in Mobile Ad Hoc Networks[J].Journal of System Simulation:2008,20(6):1523-1528.

[4] EBADI S,GHASEMBAGLOU M,NAVIN AH,Mirnia MK.Energy Balancing in Wireless Sensor Networkswith Selecting two Cluster-head Hierarchical Clustering[J]. Computational Intelligence and Communication Networks (CICN),2010:230-233.

[5] 趙小川,周正,秦智超.基于雙簇頭交替和壓縮感知的WSN路由協(xié)議[J].軟件學報,2012,23(9):17-24. ZHAO Xiao-Chuan,ZHOU Zheng,QIN Zhi-chao. Multi-Hop Routing Protocol Based on Double Cluster Head Alternation and Compressed Sensing for Wireless Sensor Networks[J].Journal of Software,2012,23(9): 17-24.

[6] 朱光輝,張修如,劉衛(wèi)彪.無線傳感器網絡中能量有效的加權分簇算法[J].傳感器與微系統(tǒng),2007,26 (12):102-105. ZHU Guang-hui,ZHANG Xiu-ru,LIUWei-biao.Energy-efficient Weighted Clustering Algorithm in Wireless Sensor Networks[J].Transducer and Microsystem Technologies,2007,26(12):102-105.

[7] 蔣青云.無線傳感器網絡簇首備份機制研究[J].計算機與現代化,2013(01):57-60. JIANG Qing-yun.Study on Cluster head Backup in Wireless Sensor Networks[J].Computers and Modernizations,2013(01):57-60.

[8] LIU Zhi-xin,ZHENG Qing-chao,XUE Liang.Energy and Node Degree Synthesized Clustering Algorithm for Wireless Sensor Networks[J].Journal of Software,2009, 20(9):250-256.

XU Xiao-tian(1988-),female,M.Sci., mainly working atmobile ad hoc networks energy -optimization algorithms.

李德敏(1963—),男,博士,教授,主要研究方向為移動計算理論及其應用、移動網絡的可靠性與安全性、信號與信息處理、移動決策理論與移動決策支持系統(tǒng);

LIDe-min(1963-),male,Ph.D.,professor,mainly working atmobile computing theory and its applications,mobile network reliability and security,signal and information processing,moile decision theory and mobile decision support system.

紫羅(1987—),女,碩士,主要研究方向為車載自組織網絡的信息融合;

Zolomaya(1987-),female,M.Sci.,mainly working at information fusion of vehicular ad-hoc network.

周凡(1990—),男,碩士,主要研究方向為無線傳感網絡的信息融合.

ZHOU Fan(1990-),male,M.Sci.,mainly working at information fusion of wireless sensor networks.

An Alternate Algorithm of Double Cluster Head based on Node Degree and Communication Costs

XU Xiao-tian1,2,LIDe-min1,2,Zolomaya1,2,ZHOU Fan1,2
(1.Department of Information Science and Technology,Donghua University,Shanghai201620,China; 2.Engineering Research Center of Digitized Textile&Fashion Technology,Ministry of Education,Shanghai201620,China)

Based on node degree and communication costs,NDCC—an alternative algorithm of double cluster head is propsoed in this paper.This algorithm is applied to solve the problem of nodes excessive-use near electronic guidemachine.The proposed NDCC incorporates double cluster head alternation system intomobile ad-hoc networks.This system chooses priority as testing standard and integrates various factors, such as taking node-degree change as the reference standard of cluster head alternation,calculating the communication costs between double-cluster head and a random nodewithin its radio range.Finally,multi -aspect simulations on NDCC algorithm with Matlab indicate the superiority of this algorithm,and some direction worthy ofmodification is also suggested in this paper.

double cluster head;node degree;communication costs

National Natural Science Foundation of China(No.71171045)

date：2014-10-14;Revised date：2015-01-07

國家自然科學基金(No.71171045)

TN911.6

1002-0802(2015)02-0171-04