基于電量均衡的無線傳感器網(wǎng)絡(luò)分簇算法
0 引 言
本文引用地址:http://www.ex-cimer.com/article/159766.htm無線傳感器網(wǎng)絡(luò)(Wireless Sensor Networks,WSN)是由任意散落在被監(jiān)測區(qū)域內(nèi)大量傳感器節(jié)點(diǎn)以自組織形式構(gòu)成的網(wǎng)絡(luò),并通過網(wǎng)絡(luò)將監(jiān)測數(shù)據(jù)傳送到接收站進(jìn)行處理。通過隨機(jī)投放的方式,眾多傳感器節(jié)點(diǎn)被密集部署于監(jiān)控區(qū)域。這些傳感器節(jié)點(diǎn)集成有傳感器、數(shù)據(jù)處理單元和通信模塊,它們通過無線信道相連,自組織地構(gòu)成網(wǎng)絡(luò)系統(tǒng)。傳感器節(jié)點(diǎn)間有良好的協(xié)作能力,通過局部的數(shù)據(jù)交換來完成全局任務(wù)。通過網(wǎng)關(guān)、傳感器網(wǎng)絡(luò)還可以連接到現(xiàn)有的網(wǎng)絡(luò)設(shè)施上(如Internet、移動通信網(wǎng)絡(luò)等),從而將采集到的信息傳回給遠(yuǎn)程的終端用戶使用。隨著微電子技術(shù)、通信技術(shù)和計(jì)算機(jī)技術(shù)的飛速發(fā)展,WSN在軍事和民用各個(gè)領(lǐng)域都得到廣泛應(yīng)用,其應(yīng)用潛力巨大,已成為目前通信領(lǐng)域的研究熱點(diǎn)。
1 無線傳感器網(wǎng)絡(luò)的拓?fù)淇刂?/p>
WSN網(wǎng)絡(luò)拓?fù)淇刂浦饕芯康膯栴}是:在保證網(wǎng)絡(luò)覆蓋度和聯(lián)通性的前提下,設(shè)置或調(diào)整節(jié)點(diǎn)的發(fā)射功率,并按照一定的原則選擇合適的節(jié)點(diǎn)成為骨干節(jié)點(diǎn),參與網(wǎng)絡(luò)中數(shù)據(jù)的處理和傳輸,達(dá)到優(yōu)化網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的目的,其首要的設(shè)計(jì)目標(biāo)是通過高效使用能量使網(wǎng)絡(luò)生命期最大化。
WSN中拓?fù)淇刂瓶梢苑譃閮蓚€(gè)研究方向:功率控制和層次拓?fù)浣Y(jié)構(gòu)控制。功率控制機(jī)制調(diào)整網(wǎng)絡(luò)中每個(gè)節(jié)點(diǎn)的發(fā)射功率,保證網(wǎng)絡(luò)連通,在均衡節(jié)點(diǎn)中直接鄰居數(shù)目(單跳可達(dá)鄰居數(shù)目)的同時(shí),降低節(jié)點(diǎn)之間的通信干擾。層次拓?fù)淇刂剖抢梅执厮枷?,使網(wǎng)絡(luò)中的部分節(jié)點(diǎn)處于激活狀態(tài),成為簇頭節(jié)點(diǎn)。由這些簇頭節(jié)點(diǎn)構(gòu)建一個(gè)連通的網(wǎng)絡(luò)來處理和傳輸網(wǎng)絡(luò)中的數(shù)據(jù),并定期或不定期地重新選擇簇頭節(jié)點(diǎn),以均衡網(wǎng)絡(luò)中節(jié)點(diǎn)的能量消耗。WSN中,節(jié)點(diǎn)的無線通信模塊處于發(fā)送狀態(tài)下功耗最高,接收狀態(tài)和空閑狀態(tài)下功耗次之,休眠狀態(tài)下功耗最低。例如,目前用于WSN的主流傳感器Berkeley Motes,其通信模塊處于發(fā)送狀態(tài)的功耗為60 mW,接收狀態(tài)和空閑狀態(tài)的功耗均為12 mW,休眠狀態(tài)的功耗為0.03 mW,其功耗比達(dá)到2 000:400:1,因此降低能耗的關(guān)鍵是降低網(wǎng)絡(luò)內(nèi)的通信流量,使更多的節(jié)點(diǎn)在更長時(shí)間段處于休眠狀態(tài)。為了大幅度降低無線通信模塊的能量消耗,可以考慮依據(jù)一定的機(jī)制選擇部分節(jié)點(diǎn)作為骨干節(jié)點(diǎn),這些節(jié)點(diǎn)的通信模塊處于打開狀態(tài),而其他非骨干節(jié)點(diǎn)的通信模塊處于關(guān)閉。在這種機(jī)制下,節(jié)點(diǎn)被分為骨干節(jié)點(diǎn)和非骨干節(jié)點(diǎn)兩類,骨干節(jié)點(diǎn)對非骨干節(jié)點(diǎn)進(jìn)行管轄。這類算法將網(wǎng)絡(luò)分為相連的區(qū)域,稱為分簇算法。
在層次拓?fù)淇刂品矫?,已?jīng)提出的算法有Deb的TopDisc(Topology Discory)拓?fù)浒l(fā)現(xiàn)算法、Santi的改進(jìn)GAF(Geographical Adaptive Fidelity)分簇算法、Heinzelman的LEACH(LOW Energy AdaptiveChlstering Hierarchy)算法和Younis的HEED算法等。
在此,以經(jīng)典的基于最小支配集理論TopDisc算法為研究對象。通過考慮節(jié)點(diǎn)電量的剩余情況,得到Power-balanced TopDisc算法。該算法將節(jié)點(diǎn)剩余能量作為分簇結(jié)構(gòu)的構(gòu)建依據(jù),對剩余能量較少的節(jié)點(diǎn)賦予一定的約束,使之成為普通節(jié)點(diǎn),從而均衡網(wǎng)絡(luò)電量負(fù)載,解決網(wǎng)絡(luò)中部分低電量節(jié)點(diǎn)擔(dān)任骨干節(jié)點(diǎn)而導(dǎo)致的能耗問題,有效延長網(wǎng)絡(luò)生命期。仿真實(shí)驗(yàn)結(jié)果證明了該算法的有效性。
2 TopDisc算法
在TopDisc算法中,首先由初始節(jié)點(diǎn)發(fā)出拓?fù)浒l(fā)現(xiàn)請求,通過廣播該請求消息來確定網(wǎng)絡(luò)中的骨干節(jié)點(diǎn),并結(jié)合這些骨干節(jié)點(diǎn)中鄰居節(jié)點(diǎn)的信息形成網(wǎng)絡(luò)拓?fù)涞慕仆負(fù)?。在這個(gè)近似拓?fù)湫纬梢院?,為了減小算法本身引起的網(wǎng)絡(luò)通信量,只有骨干節(jié)點(diǎn)才對初始節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求作出相應(yīng)的響應(yīng)。
為了確定網(wǎng)絡(luò)中的骨干節(jié)點(diǎn),TopDisc算法采用的是貪婪算法。具體分為兩種類型:三色法和四色法。
2.1 三色法
在三色算法中,節(jié)點(diǎn)可以處于三種不同狀態(tài)。在TopDisc算法中,分別用白色、黑色、灰色三種顏色表示:
(1)白色是尚未被發(fā)現(xiàn)的節(jié)點(diǎn),或者說是沒有接收到任何拓?fù)浒l(fā)現(xiàn)請求的節(jié)點(diǎn);
(2)黑色是骨干節(jié)點(diǎn)(簇頭節(jié)點(diǎn)),負(fù)責(zé)響應(yīng)拓?fù)浒l(fā)現(xiàn)請求;
(3)灰色是普通節(jié)點(diǎn),至少被一個(gè)標(biāo)記為黑色的節(jié)點(diǎn)覆蓋,即黑色節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。
在開始階段,所有節(jié)點(diǎn)都被標(biāo)記為白色,算法由一個(gè)初始節(jié)點(diǎn)發(fā)起,算法結(jié)束后所有節(jié)點(diǎn)都將被標(biāo)記為黑色或者灰色(假設(shè)整個(gè)網(wǎng)絡(luò)拓?fù)涫沁B通的)。Top-Disc使用兩種啟發(fā)式方法,使得每個(gè)新的黑色節(jié)點(diǎn)都盡可能多地覆蓋還沒有被覆蓋到的節(jié)點(diǎn):一種是節(jié)點(diǎn)顏色標(biāo)記方法;另一種是節(jié)點(diǎn)轉(zhuǎn)發(fā)拓?fù)浒l(fā)現(xiàn)請求時(shí)會故意延時(shí)一段時(shí)間,延時(shí)時(shí)間的長度反比于該節(jié)點(diǎn)與發(fā)送拓?fù)浒l(fā)現(xiàn)請求到該節(jié)點(diǎn)之間的距離。具體算法過程如下:
(1)初始節(jié)點(diǎn)被標(biāo)記為黑色,并向網(wǎng)絡(luò)廣播拓?fù)浒l(fā)現(xiàn)請求;
(2)當(dāng)白色節(jié)點(diǎn)收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí),將被標(biāo)記為灰色,并在延時(shí)時(shí)間tWB后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請求。tWB反比于它與黑色節(jié)點(diǎn)之間的距離。
(3)當(dāng)白色節(jié)點(diǎn)收到來自灰色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí),將在等待時(shí)間tWG后標(biāo)記為黑色,但如果在等待期間,又收到來自黑色節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求時(shí),則優(yōu)先標(biāo)記為灰色;同樣,等待時(shí)間反比于該白色節(jié)點(diǎn)與灰色節(jié)點(diǎn)之間的距離。不管節(jié)點(diǎn)被標(biāo)記為灰色還是黑色,都將在完成顏色標(biāo)記之后繼續(xù)廣播拓?fù)浒l(fā)現(xiàn)請求;
(4)所有已經(jīng)被標(biāo)記為黑色或者灰色的節(jié)點(diǎn),都將忽略其他節(jié)點(diǎn)的拓?fù)浒l(fā)現(xiàn)請求。
為了使每個(gè)新的黑色節(jié)點(diǎn)都盡可能多地覆蓋還沒有被覆蓋的節(jié)點(diǎn),TopDisc采用反比于節(jié)點(diǎn)之間距離的轉(zhuǎn)發(fā)延時(shí)機(jī)制。理想情況下,節(jié)點(diǎn)的覆蓋范圍是半徑為無線電發(fā)射半徑的圓。于是,單個(gè)節(jié)點(diǎn)所能夠覆蓋的節(jié)點(diǎn)數(shù)目正比于其覆蓋面積和局部節(jié)點(diǎn)部署密度。對于一個(gè)正在轉(zhuǎn)發(fā)拓?fù)浒l(fā)現(xiàn)請求的節(jié)點(diǎn),它所能夠覆蓋的新節(jié)點(diǎn)(還沒有被任何節(jié)點(diǎn)覆蓋)則正比于它的覆蓋面積與已經(jīng)覆蓋的面積之差。
評論