無線傳感器網(wǎng)絡(luò)分簇路由中基于自適應(yīng)的簇頭輪換算法*

馮 咲,張慧檔

(河南工業(yè)大學(xué)信息科學(xué)與工程學(xué)院,鄭州 450001)

無線傳感器網(wǎng)絡(luò)WSNs(Wireless Sensor Networks)是由大量隨機(jī)部署的傳感器節(jié)點(diǎn)通過無線通訊方式自組織形成的一種多跳網(wǎng)絡(luò)。周期性采集型無線傳感器網(wǎng)絡(luò)是一種最常見的應(yīng)用模式,其目的是周期性感知和處理網(wǎng)絡(luò)覆蓋區(qū)域內(nèi)的環(huán)境信息。WSN的物理層和MAC層遵循IEEE 802.15.4標(biāo)準(zhǔn)[1],其網(wǎng)絡(luò)層的路由協(xié)議面臨節(jié)點(diǎn)能量受限問題。

由于節(jié)點(diǎn)能量受限,因此低能耗路由設(shè)計(jì)是WSNs的一個(gè)關(guān)鍵問題[2]。層次路由是低能耗路由的有效解決方案[3]。分簇路由是典型的層次路由,其中,網(wǎng)絡(luò)被劃分成多個(gè)簇,每個(gè)簇有一個(gè)簇頭和若干個(gè)簇成員組成。簇頭負(fù)責(zé)簇內(nèi)信息收集和簇間數(shù)據(jù)轉(zhuǎn)發(fā),簇成員負(fù)責(zé)信息感知。簇之間相互連接構(gòu)成一個(gè)以匯聚節(jié)點(diǎn)為根的簇樹。分簇路由具有很強(qiáng)的結(jié)構(gòu)性,因此它特別適合采用休眠/喚醒機(jī)制的周期性采集型無線傳感器網(wǎng)絡(luò)。

目前已提出多種分簇算法,LEACH是最著名的分簇算法;該算法基于閾值隨機(jī)選取一組節(jié)點(diǎn)作為簇頭進(jìn)行分簇;為了平衡節(jié)點(diǎn)能耗,該文獻(xiàn)還提出了簇頭輪換的概念[4]。DCPVP算法基于表決和優(yōu)先理念實(shí)現(xiàn)了分布式分簇[5]。DCMDC 算法基于網(wǎng)絡(luò)服務(wù)區(qū)域劃分實(shí)現(xiàn)了自適應(yīng)動(dòng)態(tài)分簇[6];EACHP算法基于能量感知模型實(shí)現(xiàn)了多級分簇[7]。廖福保和張文梅在文獻(xiàn)[8]中給出了一個(gè)基于最小生成樹的非均勻分簇路由協(xié)議。文獻(xiàn)[9-10]基于模糊邏輯對WSNs的聚類分析進(jìn)行了研究。上述分簇算法在分簇過程中均沒有考慮分簇?cái)?shù)量的優(yōu)化,存在冗余簇頭。

由于簇頭需要維護(hù)路由,不能進(jìn)入休眠狀態(tài);簇成員在非自己的采樣時(shí)隙內(nèi)可以處于低功耗休眠狀態(tài),因此,簇頭能耗要遠(yuǎn)大于成員能耗。分簇路由的設(shè)計(jì)面臨兩個(gè)挑戰(zhàn):一是盡可能減少簇頭的數(shù)量,二是應(yīng)該有有效的簇頭輪換策略。

針對第1個(gè)挑戰(zhàn),利用連通支配集(CDS)構(gòu)造簇頭集合是減少簇頭數(shù)量的有效方法[11]。然而,求解最小連通支配集MCDS(Minimum Connected Dominating Set)是一個(gè)NPC問題[12]。目前學(xué)者們提出了多種構(gòu)造近似MCDS的方法:Guha和Khuller提出了兩個(gè)近似MCDS的構(gòu)造算法[13];Deb B 等人基于CDS提出了一個(gè)WSNs的拓?fù)浒l(fā)現(xiàn)的算法TopDisc[14];文獻(xiàn)[15-22]專注于構(gòu)造最小規(guī)模CDS、負(fù)載平衡的CDS、有界直徑的CDS、k-覆蓋的CDS或最小路由代價(jià)的CDS等方面。上述文獻(xiàn)在構(gòu)造CDS時(shí)均忽視了節(jié)點(diǎn)的能量,而節(jié)點(diǎn)的能量決定了CDS的壽命。本文基于節(jié)點(diǎn)的能量和節(jié)點(diǎn)的度,提出了一個(gè)構(gòu)造CDS的算法,并基于該CDS提出了一個(gè)簇樹構(gòu)造算法CDS-CTCA(Cluster Tree Construction Algorithm based on CDS)。

針對第2個(gè)挑戰(zhàn),在文獻(xiàn)[4]中已經(jīng)提出了簇頭輪換的概念,但是沒有給出如何計(jì)算簇頭輪換間隔的方法,本文基于簇樹工作周期的預(yù)測提出了一個(gè)簇頭輪換間隔的優(yōu)化算法,實(shí)現(xiàn)了自適應(yīng)簇頭輪換機(jī)制。本文的主要貢獻(xiàn)為:①基于簇樹工作周期的概念,提出了一個(gè)簇頭輪換間隔的優(yōu)化算法,實(shí)現(xiàn)了自適應(yīng)簇頭輪換機(jī)制;②提出了一個(gè)基于CDS的簇樹構(gòu)造算法,減少了簇頭數(shù)量,節(jié)約了網(wǎng)絡(luò)能耗。

1 準(zhǔn)備工作

在本節(jié)中,我們首先介紹幾個(gè)術(shù)語,然后討論周期性采集型WSN模型,最后給出消息類型。

1.1 相關(guān)術(shù)語

①連通支配集(CDS):定義見文獻(xiàn)[13]。CDS中的節(jié)點(diǎn)稱作支配節(jié)點(diǎn),它在WSN中起著骨干作用,因此,CDS又稱作虛擬骨干網(wǎng)。本文中支配節(jié)點(diǎn)、骨干節(jié)點(diǎn)和簇頭節(jié)點(diǎn)是等價(jià)的。

②節(jié)點(diǎn)鄰居集:能夠和節(jié)點(diǎn)直接通訊的節(jié)點(diǎn)集合稱為節(jié)點(diǎn)的鄰居集。

③節(jié)點(diǎn)級別:在層次路由中節(jié)點(diǎn)距離匯聚節(jié)點(diǎn)的跳數(shù)稱為節(jié)點(diǎn)的級別。匯聚節(jié)點(diǎn)的級別為0。

④節(jié)點(diǎn)狀態(tài):我們用4種顏色表示節(jié)點(diǎn)的4種狀態(tài)。其意義如下:

White:當(dāng)一個(gè)節(jié)點(diǎn)未接收到其他節(jié)點(diǎn)任何消息時(shí)的狀態(tài);

Black:當(dāng)一個(gè)節(jié)點(diǎn)為支配節(jié)點(diǎn)時(shí)的狀態(tài);

Grey:當(dāng)一個(gè)節(jié)點(diǎn)為Black節(jié)點(diǎn)的鄰居時(shí)的狀態(tài);

Dark-Grey:在Black節(jié)點(diǎn)的鄰居集中,能量大于平均能量的節(jié)點(diǎn)的狀態(tài)。

說明:本文中有時(shí)用顏色名稱代替對應(yīng)狀態(tài)的節(jié)點(diǎn)。

⑤節(jié)點(diǎn)采樣周期:節(jié)點(diǎn)兩次相鄰的采樣間隔,記作SP(sampling period)。

⑥簇樹構(gòu)造周期:在分簇路由中,構(gòu)造一個(gè)簇樹所需的時(shí)間,記作CTCP(Cluster Tree Construction Period。

⑦簇樹工作周期:一個(gè)簇樹從開始運(yùn)行到下一次重構(gòu)的間隔,記作CTWP(cluster tree working period。當(dāng)簇樹重構(gòu)時(shí),簇頭將隨之更換,因此簇樹工作周期就是簇頭輪換間隔。

1.2 周期性采集型WSN模型

在周期性采集型WSN中的所有傳感器節(jié)點(diǎn)具有相同的采樣周期。本文討論的網(wǎng)絡(luò)模型為周期性采集型WSN,具體描述如下:

圖1 傳感器節(jié)點(diǎn)部署示意圖

傳感器網(wǎng)絡(luò)由1個(gè)匯聚節(jié)點(diǎn)和N個(gè)傳感器節(jié)點(diǎn)組成。N個(gè)傳感器節(jié)點(diǎn)隨機(jī)部署在一個(gè)100 m×60 m的監(jiān)控區(qū)域中,匯聚節(jié)點(diǎn)位于監(jiān)控區(qū)域的外側(cè),如圖1 所示。匯聚節(jié)點(diǎn)能量無限,傳感器節(jié)點(diǎn)能量受限。傳感器節(jié)點(diǎn)同構(gòu),具有相同的發(fā)射半徑R,并且每個(gè)傳感器節(jié)點(diǎn)與匯聚節(jié)點(diǎn)之間至少存在一條通訊路徑。此時(shí),無線傳感器網(wǎng)絡(luò)可以抽象為一個(gè)單位圓盤圖(UDG),用G=(V,E)表示。其中,V為頂點(diǎn)集合,表示網(wǎng)絡(luò)中所有節(jié)點(diǎn)的集合;E為邊的集合,表示網(wǎng)絡(luò)中所有可以直接通訊的節(jié)點(diǎn)對(u,v)的集合。當(dāng)R=25 m時(shí),網(wǎng)絡(luò)的通訊連通圖如圖2所示。

圖2 網(wǎng)絡(luò)連通示意圖

1.3 消息類型

本文設(shè)計(jì)的消息類型分為3組,分別用于簇頭選舉、聚類成簇和數(shù)據(jù)傳輸。

(1)用于簇頭選舉的消息:

①Black-query-White-with-State-and-Level:Black節(jié)點(diǎn)查詢White節(jié)點(diǎn)的消息,該消息包含Black節(jié)點(diǎn)的狀態(tài)和級別;

②Grey-answer-Black-with-Energy:Grey鄰居對Black節(jié)點(diǎn)的應(yīng)答消息,該消息包含Grey的剩余能量;

③Black-announce-Grey-isDarkGrey:Black節(jié)點(diǎn)宣布Dark-Grey節(jié)點(diǎn)的選舉結(jié)果;

④DarkGrey-query-White:Dark-Grey節(jié)點(diǎn)查詢White節(jié)點(diǎn)的消息;

⑤White-answer-DarkGrey:White鄰居對Dark-Grey節(jié)點(diǎn)的應(yīng)答消息;

⑥D(zhuǎn)arkGrey-report-WhiteNeighbors-to-Sink:Dark-Grey節(jié)點(diǎn)向匯聚節(jié)點(diǎn)匯報(bào)它們的White鄰居信息的消息;

⑦Sink-announce-DarkGrey-isBlack:匯聚節(jié)點(diǎn)宣布Black節(jié)點(diǎn)的選舉結(jié)果;

(2)用于聚類的消息:

①Black-declare-isClusterHead-to-Network-with-Level:Black節(jié)點(diǎn)向網(wǎng)絡(luò)聲明它們是簇頭的消息,該消息包含Black的級別;

②ordinaryNode-associate-ClusterHead:普通節(jié)點(diǎn)(Grey 節(jié)點(diǎn)或 Dark-Grey節(jié)點(diǎn))關(guān)聯(lián)簇頭的消息;

③ClusterHead-allot-Ordinal-to-Member:簇頭為成員分配簇內(nèi)序號的消息;

④ClusterHead-report-Members-and-Energy-to-Sink:簇頭向匯聚節(jié)點(diǎn)匯報(bào)它們的簇成員和它們的剩余能量信息的消息。

(3)用于數(shù)據(jù)傳輸?shù)南?

①Sink-broadcast-CTWP-to-Network:匯聚節(jié)點(diǎn)廣播該簇樹工作周期的消息;

②Sensor-transmit-Data-to-Sink:傳感器節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳送數(shù)據(jù)的消息。

2 基于連通支配集的簇樹構(gòu)造算法

CDS-CTCA算法分兩個(gè)階段,第1個(gè)階段構(gòu)造出一個(gè)CDS;第2個(gè)階段普通節(jié)點(diǎn)通過CDS聚類成簇樹。

2.1 構(gòu)造CDS

初始化時(shí),傳感器節(jié)點(diǎn)狀態(tài)為White,匯聚節(jié)點(diǎn)的狀態(tài)為Black。算法從Black節(jié)點(diǎn)開始進(jìn)行迭代直至網(wǎng)絡(luò)中不存在White節(jié)點(diǎn)為止。每次迭代中,首先標(biāo)記Black節(jié)點(diǎn)的White鄰居為Grey,然后標(biāo)記其中能量大于鄰居集的平均能量的節(jié)點(diǎn)為Dark-Grey,最后標(biāo)記擁有最多White鄰居的Dark-Grey節(jié)點(diǎn)為Black。具體算法如下:

①所有傳感器節(jié)點(diǎn)初始化為White;匯聚節(jié)點(diǎn)初始化為Black,級別為0;

②Black節(jié)點(diǎn)廣播Black-query-White-with-State-and-Level消息。接收到該消息的White-節(jié)點(diǎn)變成Grey,級別為Black節(jié)點(diǎn)的級別加1。然后通過Grey-answer-Black-with-Energy消息應(yīng)答B(yǎng)lack節(jié)點(diǎn);

③規(guī)定時(shí)限結(jié)束后,Black-節(jié)點(diǎn)從其Grey鄰居集中找出能量大于平均能量的節(jié)點(diǎn)作為Dark-Grey節(jié)點(diǎn),并通過Black-announce-Grey-isDarkGrey消息宣布選擇結(jié)果;

④接收Black-announce-Grey-isDarkGrey消息后,對應(yīng)的Grey節(jié)點(diǎn)變成Dark-Grey;

⑤Dark-Grey節(jié)點(diǎn)廣播DarkGrey-query-White消息。接收到該消息的White節(jié)點(diǎn)通過White-answer-DarkGrey消息進(jìn)行應(yīng)答;

⑥D(zhuǎn)ark-Grey節(jié)點(diǎn)通過接收White-answer-DarkGrey消息統(tǒng)計(jì)它的White鄰居數(shù),規(guī)定時(shí)限結(jié)束后,通過DarkGrey-report-WhiteNeighbors-to-Sink消息將其White鄰居數(shù)上傳給匯聚節(jié)點(diǎn);

⑦匯聚節(jié)點(diǎn)選出擁有最多White鄰居的Dark-Grey節(jié)點(diǎn)作為本次迭代的Black節(jié)點(diǎn),在規(guī)定時(shí)限結(jié)束后,通過Sink-inform-DarkGrey-isBlack消息宣布選舉結(jié)果;

⑧接收到Sink-announce-DarkGrey-isBlack消息后,對應(yīng)的Dark-Grey節(jié)點(diǎn)變?yōu)锽lack;

⑨判斷區(qū)域內(nèi)是否還存在White節(jié)點(diǎn),若存在,則轉(zhuǎn)②,否則結(jié)束迭代。

上述算法最后得到的Black節(jié)點(diǎn)集合即為CDS。

例如,圖1中所示的WSN,若所有傳感器節(jié)點(diǎn)的初始能量相同,利用上述算法首次構(gòu)造的CDS如圖3所示,其中黑色節(jié)點(diǎn)為支配節(jié)點(diǎn)。由于支配節(jié)點(diǎn)能耗大于普通節(jié)點(diǎn),因此充當(dāng)過支配節(jié)點(diǎn)的節(jié)點(diǎn)的能量要小于平均能量。在下次構(gòu)造CDS時(shí),它不能繼續(xù)充當(dāng)支配節(jié)點(diǎn)。第2次構(gòu)造CDS的迭代過程如圖4所示,其中黑色節(jié)點(diǎn)為支配節(jié)點(diǎn),圖4(2)-(6)為CDS-CTCA算法逐次迭代的結(jié)果。

圖3 CDS-CTCA算法第1次構(gòu)造的CDS

圖4 CDS-CTCA第2次重構(gòu)CDS的過程

2.2 聚類成簇樹

CDS構(gòu)造之后,CDS-CTCA算法進(jìn)入聚類階段。

首先,Black節(jié)點(diǎn)向網(wǎng)絡(luò)聲明它們是簇頭,然后,普通節(jié)點(diǎn)(Grey節(jié)點(diǎn)或Dark-Grey節(jié)點(diǎn))在其簇頭鄰居中選擇級別最低且距離最近(根據(jù)RSSI強(qiáng)度)的簇頭進(jìn)行關(guān)聯(lián),成為該簇頭的一個(gè)簇成員。具體算法如下:

①Black節(jié)點(diǎn)通過Black-declare-isClusterHead-to-Network-with-Level消息聲明它們是簇頭,在它們通訊范圍內(nèi)的普通節(jié)點(diǎn)接收該消息并記錄Black節(jié)點(diǎn)的級別;

②規(guī)定時(shí)限結(jié)束后,每個(gè)普通節(jié)點(diǎn)從它的簇頭鄰居集中選擇級別最低且距離最近的簇頭通過ordinaryNode-associate-ClusterHead消息請求關(guān)聯(lián);

③接收到該關(guān)聯(lián)請求消息的簇頭通過ClusterHead-allot-Ordinal-to-Member消息為該成員分配一個(gè)簇內(nèi)序號;

④所有的簇頭通過ClusterHead-report-Members-and-Energy-to-Sink消息向匯聚節(jié)點(diǎn)匯報(bào)它們的簇成員和剩余能量信息。

普通節(jié)點(diǎn)聚類到CDS之后就構(gòu)造了一個(gè)簇樹。例如,圖3和圖4中的CDS通過上述算法聚類而成的簇樹如圖5和圖6所示。

圖5 CDS-CTCA算法第1次構(gòu)造的簇樹

圖6 CDS-CTCA算法第2次重構(gòu)的簇樹

2.3 簇樹工作工作過程

簇樹生成后,匯聚節(jié)點(diǎn)計(jì)算該簇樹的工作周期,并通過Sink-broadcast-CTWP-to-Network消息廣播給網(wǎng)絡(luò),然后,簇樹進(jìn)入工作階段。在簇樹工作階段,簇頭依照TDMA時(shí)隙(Slot)順序收集本簇成員的數(shù)據(jù),經(jīng)融合處理后逐跳沿樹上傳到匯聚節(jié)點(diǎn)。當(dāng)該簇樹的工作周期結(jié)束后進(jìn)行簇頭輪換,即重構(gòu)簇樹。第4節(jié)中討論簇頭輪換的策略。

3 自適應(yīng)簇頭輪換

簇頭輪換的概念最先由文獻(xiàn)[4]提出,但它沒有給出如何計(jì)算輪換間隔的方法。本節(jié)中我們提出的簇頭輪換間隔的優(yōu)化算法是對文獻(xiàn)[4]一個(gè)補(bǔ)充。

3.1 節(jié)點(diǎn)的運(yùn)行過程

在周期性采集型WSN分簇算法中,為了平衡節(jié)點(diǎn)的能耗,通常采用簇頭輪換機(jī)制。在基于簇頭輪換機(jī)制的周期性采集型WSN中,任意一節(jié)點(diǎn)的運(yùn)行過程如圖7所示。

由圖7可以看出,一個(gè)簇樹工作周期(CTWP)等于任一節(jié)點(diǎn)在其內(nèi)部的采樣周期(SP)之和。因此只要預(yù)測出一個(gè)節(jié)點(diǎn)在CTWP內(nèi)的采樣輪數(shù),即可計(jì)算出CTWP的大小。節(jié)點(diǎn)在CTWP內(nèi)的采樣輪數(shù)與該節(jié)點(diǎn)在SP內(nèi)的能耗成反比,與該節(jié)點(diǎn)在簇樹構(gòu)造后的剩余能量成正比。由于簇頭能耗大于普通節(jié)點(diǎn)能耗,因此簇頭的采樣輪數(shù)決定了CTWP的大小。在4.2節(jié)中以TICC2530節(jié)點(diǎn)能耗模型為例分析了簇頭在SP內(nèi)的能耗;4.3節(jié)給出了CTWP的優(yōu)化算法。

圖7 節(jié)點(diǎn)在簇頭輪換機(jī)制的WSN中的運(yùn)行過程

3.2 簇頭在SP內(nèi)的能耗分析

本節(jié)以TICC2530節(jié)點(diǎn)的能耗模型為例分析簇頭在一個(gè)SP內(nèi)的能耗。TICC2530片上系統(tǒng)符合IEEE802.15.4標(biāo)準(zhǔn)[1]。當(dāng)工作在2.4 GHz頻道上時(shí),數(shù)據(jù)傳輸率為250 kbyte/s,因此傳輸1b數(shù)據(jù)所用時(shí)間為

T1b=1/(250×1 000)=4×10-6s。

表1為德克薩斯儀器公司給出的TICC2530 SoC的電器特性[23]。由于簇頭需要維護(hù)路由,因此它的32 MHz晶振需要一直處于運(yùn)行狀態(tài)。簇頭在SP內(nèi)的能耗包括4個(gè)部分:傳感器能耗、CPU能耗、接收機(jī)能耗和發(fā)射機(jī)能耗。TICC2530的電特性采用典型數(shù)值,簇頭在SP內(nèi)的各部分能耗分析如下:

①傳感器能耗:簇頭是一個(gè)傳感器節(jié)點(diǎn),因此它也需要在它的采樣時(shí)隙內(nèi)驅(qū)動(dòng)傳感器進(jìn)行數(shù)據(jù)采集,這部分能耗用E(S)表示。如一個(gè)TICC2530和一個(gè)DS18B20組成的溫度傳感器節(jié)點(diǎn),TICC2530驅(qū)動(dòng)DS18B20的能耗可由式(1)計(jì)算[24]:

E(S)=IDQA×tCONV=1 mA×0.75 s=0.75 mAs

(1)

②CPU能耗:在一個(gè)SP內(nèi),簇頭的CPU需要處理信息和計(jì)算數(shù)據(jù),這部分能耗用E(C)表示,它可用下列公式計(jì)算:

E(C)=IC×SP=6.5 SP(mAs)

(2)

③接收機(jī)能耗:設(shè)Sensor-transmit-Data-to-Sink消息的長度為L,簇頭的后代節(jié)點(diǎn)數(shù)為K(0≤K≤N,N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù))。在一個(gè)SP內(nèi),簇頭的接收機(jī)接收后代節(jié)點(diǎn)數(shù)據(jù)的能耗用E(R)用式(3)計(jì)算:

E(R)=KLT1bIRx=4×10-6×24.3KL=
9.72×10-5KL(mAs)

(3)

④發(fā)射機(jī)能耗:條件同③款,在一個(gè)SP內(nèi),簇頭的發(fā)射機(jī)轉(zhuǎn)發(fā)后代節(jié)點(diǎn)數(shù)據(jù)的能耗E(T)可用式(4)計(jì)算:

E(T)=KLT1bITx=4×10-6×28.7KL=
1.148×10-4KL(mAs)

(4)

通過上述分析,簇頭在一個(gè)SP內(nèi)的能耗 ESP(CH) 可用式(5)計(jì)算:

ESP(CH)=E(S)+E(C)+E(R)+E(T)=
E(S)+6.5 SP+9.72×10-5KL+1.148×10-4KL=
E(S)+6.5 SP+2.12×10-4KL(mAs)

(5)

因?yàn)?≤K≤N,所以

E(S)+6.5 SP≤ESP(CH)≤
E(S)+6.5 SP+2.12×10-4NL

(6)

式中:SP,N,L和E(S)都是常數(shù)。簇頭在SP內(nèi)的能耗ESP(CH)可用式(5)的中位值近似表示,即

ESP(CH)=E(S)+6.5 SP+1.06×10-4NL(mAs)

(7)

表1 TICC2530電器特性

3.3 簇樹工作周期優(yōu)化算法

由式(7)可以看出簇頭在一個(gè)SP內(nèi)的能耗近似為一個(gè)常數(shù)。根據(jù)4.1節(jié)的分析,一個(gè)簇樹的采樣輪數(shù)由擁有最小剩余能量的簇頭決定。簇頭的剩余能量可以從ClusterHead-report-Members-and-Energy-to-Sink消息中獲得。簇頭集合中最小的剩余能量用Emax(CH)表示,則

(8)

因此,該簇樹最多能進(jìn)行Emax(CH)/ESP(CH)輪采樣。為了保證簇頭能量不被耗盡,可乘以一個(gè)小于1的因子來優(yōu)化簇樹的采樣輪數(shù),即

(9)

式中:Round(CTWP)為簇樹的優(yōu)化采樣輪數(shù),Int為取整函數(shù),α為簇樹重構(gòu)因子(或簇頭輪換因子),其取值范圍為(0,1)。

參照圖7,簇樹的工作周期CTWP可由式(10)計(jì)算:

CTWP=SP×Round(CTWP)

(10)

說明:在實(shí)際操作中,用簇樹的采樣輪數(shù)代替簇樹的工作周期(或簇頭的輪換間隔)更為方便。

3.4 自適應(yīng)簇頭輪換算法

在數(shù)據(jù)傳輸階段,任意一個(gè)傳感器節(jié)點(diǎn)完成Round(CTWP)輪采樣之后,將自己的狀態(tài)設(shè)置White進(jìn)入簇頭輪換階段,即重構(gòu)簇樹階段。自適應(yīng)簇頭輪換過程描述如下:

①傳感器節(jié)點(diǎn)基于CDS-CTCA算法構(gòu)造一個(gè)簇樹;

②匯聚節(jié)點(diǎn)依據(jù)式(9)計(jì)算Round(CTWP),并廣播給網(wǎng)絡(luò);

③傳感器節(jié)點(diǎn)向匯聚節(jié)點(diǎn)傳送采樣數(shù)據(jù);

④傳感器節(jié)點(diǎn)判斷是否完成Round(CTWP)輪采樣,若是,則狀態(tài)設(shè)為White,轉(zhuǎn)①;否則,轉(zhuǎn)③。

4 仿真評估

在本節(jié)中,通過仿真實(shí)驗(yàn)評估CDS-CTCA算法所構(gòu)造的CDS的性能和自適應(yīng)簇頭輪換算法的性能。

4.1 CDS性能評估

仿真環(huán)境:傳感器節(jié)點(diǎn)隨機(jī)部署于100 m×60 m的矩形區(qū)域內(nèi),匯聚節(jié)點(diǎn)部署在區(qū)域外側(cè),如圖1所示;傳感器節(jié)點(diǎn)同構(gòu),具有相同的發(fā)射半徑R=25 m。

圖9 CDS直徑對比示意圖

仿真內(nèi)容:節(jié)點(diǎn)個(gè)數(shù)分別取50,100,150,200,250和300。對每組節(jié)點(diǎn)利用MATLAB軟件分別運(yùn)行CDS-CTCA、TopDisc和Guha 1各10次。

仿真目標(biāo):①CDS規(guī)模:指CDS中的節(jié)點(diǎn)個(gè)數(shù);②CDS直徑:指CDS中的節(jié)點(diǎn)的最高級別。

仿真結(jié)果:3種算法分別運(yùn)行十次得到的CDSs的規(guī)模和CDSs的直徑的平均值對比如圖8和圖9所示。

圖8 CDS規(guī)模對比示意圖

結(jié)果分析:從圖8和圖9中可以看出,TopDisc算法構(gòu)造的CDS規(guī)模最大,直徑最長。這是因?yàn)門opDisc算法是基于節(jié)點(diǎn)之間的距離構(gòu)造CDS的。而CDS的規(guī)模與節(jié)點(diǎn)間的距離沒有直接關(guān)系,與節(jié)點(diǎn)的覆蓋度直接相關(guān)。也就說,兩個(gè)相對較遠(yuǎn)的節(jié)點(diǎn)未必有較大的節(jié)點(diǎn)覆蓋度。

Guha 1算法是以最大度節(jié)點(diǎn)為第1個(gè)支配節(jié)點(diǎn)構(gòu)造CDS的,但這樣做會(huì)將網(wǎng)絡(luò)中其他節(jié)點(diǎn)劃分成很多碎片,導(dǎo)致其他支配節(jié)點(diǎn)具有較小的度。CDS-CTCA算法是從匯聚節(jié)點(diǎn)開始構(gòu)造CDS的,這樣做有三方面的好處:①使匯聚節(jié)點(diǎn)承擔(dān)盡可能多的任務(wù),不會(huì)影響網(wǎng)絡(luò)總能耗;②減少支配節(jié)點(diǎn)到匯聚節(jié)點(diǎn)的跳數(shù),即減小CDS的直徑;③減少分離碎片,使支配節(jié)點(diǎn)負(fù)載相對均勻。因此CDS-CTCA算法比Guha1更優(yōu)。

4.2 自適應(yīng)簇頭輪換算法性能評估

仿真環(huán)境:與4.1節(jié)中的環(huán)境相同;

仿真參數(shù):如表2所示。

表2 仿真參數(shù)

仿真內(nèi)容:節(jié)點(diǎn)個(gè)數(shù)分別取50、100、150、200、250和300;構(gòu)造簇樹采用CDS-CTCA算法;簇頭輪換策略為定長間隔輪換和自適應(yīng)間隔輪換;定長間隔輪換策略的采樣輪數(shù)分別取100、800、1 500和2 200。

仿真目標(biāo):①網(wǎng)絡(luò)生存周期:指出現(xiàn)節(jié)點(diǎn)死亡或簇頭不能完全覆蓋網(wǎng)絡(luò)時(shí)網(wǎng)絡(luò)的運(yùn)行時(shí)間;②能量效率:指網(wǎng)絡(luò)生存周期結(jié)束后,用于傳輸數(shù)據(jù)的能耗與網(wǎng)絡(luò)初始總能量之比,即

仿真結(jié)果:網(wǎng)絡(luò)生存周期仿真結(jié)果如圖10所示,能耗效率仿真結(jié)果如圖11所示。

結(jié)果分析:由圖10和圖11可以看出,重構(gòu)間隔為100輪采樣時(shí)網(wǎng)絡(luò)壽命較短,網(wǎng)絡(luò)能量利用率較低,這是因?yàn)橹貥?gòu)間隔太短導(dǎo)致簇頭輪換頻繁,從而消耗了大量的網(wǎng)絡(luò)能量;重構(gòu)間隔為2 200輪采樣時(shí)網(wǎng)絡(luò)壽命最短,網(wǎng)絡(luò)利用率最低,這是因?yàn)榇仡^工作時(shí)間太長,在輪換之前就已死亡;重構(gòu)間隔為800輪和1 500輪采樣時(shí),雖然獲得了較長網(wǎng)絡(luò)壽命和較大的網(wǎng)絡(luò)能量利用率,但不是最佳的;自適應(yīng)簇頭輪換算法的輪換間隔是動(dòng)態(tài)的,每個(gè)簇樹都具有優(yōu)化的運(yùn)行周期,因此獲得了最長的網(wǎng)絡(luò)壽命。

圖10 網(wǎng)絡(luò)生存周期對比示意圖

圖11 網(wǎng)絡(luò)能量有效利用率對比

4.3 簇頭輪換因子對網(wǎng)絡(luò)壽命的影響

簇頭輪換因子的取值過大或過小都將縮短網(wǎng)絡(luò)壽命,一般需要通過實(shí)驗(yàn)獲得合適數(shù)值。在與5.2小節(jié)相同條件下,圖12表示了簇頭輪換因子對網(wǎng)絡(luò)壽命的影響。從圖12可以看出,在傳感器節(jié)點(diǎn)數(shù)小于300時(shí),簇頭輪換因子取0.9,網(wǎng)絡(luò)壽命較長。在后續(xù)工作中,我們將探討自適應(yīng)簇頭輪換因子的設(shè)計(jì)方法。

圖12 簇頭輪換因子對網(wǎng)絡(luò)壽命的影響

5 結(jié)束語

為了預(yù)估分簇路由中簇頭的輪換間隔,本文以TICC2530 SoC的能耗模型為例分析了簇樹的工作周期,提出了基于簇樹工作周期的簇頭輪換優(yōu)化算法,實(shí)現(xiàn)了自適應(yīng)簇頭輪換機(jī)制。另外,為了減少簇頭數(shù)量,節(jié)省網(wǎng)絡(luò)總能耗,本文提出了一個(gè)基于CDS的構(gòu)造簇樹算法。仿真結(jié)果驗(yàn)證了本文提出的簇樹構(gòu)造算法和自適應(yīng)簇頭輪換算法的有效性。下一步的工作重點(diǎn)是將本文提出的算法應(yīng)用于工程實(shí)踐中,進(jìn)一步驗(yàn)證算法的可行性。

參考文獻(xiàn):

[1] IEEE. IEEE 802.15 WPAN Task Group4(TG4)[S]. http://www.ieee802.org/15/pub/TG4.html. 2016.

[2] LEE SL,CHENG WL. Fuzzy-Logic-Based Clustering Approach for Wireless Sensor Networks Using Energy Predication[J]. IEEE Sensors Journal,2012,12(9):2891-2897.

[3] LIU X X. Atypical Hierarchical Routing Protocols for Wireless Sensor Networks:A Review[J]. IEEE Sensors Journal,2015,15(10):5372-5383.

[4] Heinzelman W,Chandrakasan A,Balakrishnan H. Energy-Efficient Communication Protocol for Wireless Microsensor Networks[C]//Hawaii International Conference on System Sciences,2000,3005-3014.

[5] Abuarqoub A,Hammoudeh M,Adebisi B et al.Dynamic Clustering and Management of Mobile Wireless Sensor Networks[J]. Computer Networks,2017,117:62-75.

[6] Chang Y C,Tang H Y,Cheng Y B,et al. Dynamic Hierarchical Energy-Efficient Method Based on Combinatorial Optimization for Wireless Sensor Networks[J]. Sensors,2017,17(7):1665.

[7] Barati H,Hovaghar A,Rahmani A M. EACHP:Energy Aware Clustering Hierarchy Protocol for Large Scale Wireless Sensor Networks[J]. Wireless Personal Communications,2015,83(3):765-789.

[8] 廖福保,張文梅. 基于最小生成樹的非均勻分簇路由協(xié)議[J]. 傳感技術(shù)學(xué)報(bào),2017,30(9):1412-1416.

[9] Nayak P,Devulapalli A. A Fuzzy Logic-Based Clustering Algorithm for WSN to Extend the Network Lifetime[J]. IEEE Sensors Journal,2016,16(1):137-144.

[10] Song X Y,Zhang Q L,Sun W,et al. Energy-Efficient Data Gathering Protocol in Unequal Clustered WSN Utilizing Fuzzy Multiple Criteria Decision Making[J]. Journal of Intelligent and Fuzzy Systems,2017,32(5):3461-3473.

[11] Spohn M A,Garcia-Luna-Aceves J J. Bounded-Distance Multi-Clusterhead Formation in Wireless ad hoc Networks[J]. Ad Hoc Networks,2007,5(4):504-530.

[12] Darey M R,Johnson D S. Computers and Intractability:A Guide to the Theory of NP-Completeness[M]. W H Freeman and Co. New York,NY,USA 1979:206-218.

[13] GUHA S,KHULLER S. Approximation Algorithms for Connected Dominating Sets[J]. Algorithmica,1998,20:374-387.

[14] Deb B,Bhatnagar S,Nath B. A Topology Discovery Algorithm for Sensor Networks with Applications to Network Management[R]. DCS Technical Report,DCS-TR-411,Rutgers University,2001:26-30.

[15] Torkestani J A. Backbone Formation in Wireless Sensor Networks[J]. Sensors and Actuators A—Physical,2013,185:117-126.

[16] He J,Ji S L,Pan Y,et al. Greedy Construction of Load-Balanced Virtual Backbones in Wireless Sensor Networks[J]. Wireless Communications and Mobile Computing,2014,14(7):673-688.

[17] Zhang J,Xu L,Zhou S M,et al. An Efficient Connected Dominating Set Algorithm in Wsns Based on The Induced Tree of The Crossed Cube[J]. International Journal of Applied Mathematics and Computer Science,2015,25(2):295-309.

[18] Ramar R,Shanmugasundaram R. Connectedk-Coverage Topology Control for Area Monitoring in Wireless Sensor Networks[J]. Wireless Personal Communications,2015,84(2):1051-1067.

[19] Yang Sm,Tang W. A Highly Efficient Distributed Algorithm for Constructing CDS with Opportunistic Announcement in Wireless Sensor Networks[C]//18th UKSim-AMSS International Conference on Computer Modelling and Simulation,UKSim,2016:317-322.

[20] Shi Y S,Zhang Y P,Zhang Z,et al. A greedy algorithm for the Minimum 22-Connected mm-fold Dominating Set Problem[J]. Journal of Combinatorial Optimization,2016,31(1):136-151.

[21] Mohanty J P,Mandal C,Reade C. Distributed Construction of Minimum Connected Dominating Set in wireless Sensor Network Using Two-Hop Information[J]. Computer Networks,2017,123:137-152.

[22] Zhang J,Xu L,Xue X S,et al. Virtual Backbone Scheduling with Connected Domatic Partition inWireless Sensor Networks[J]. Ad Hoc and Sensor Wireless Networks,2017,38(1-4):169-198.

[23] Texas Instruments Incorporated. A True System-on-Chip Solution for 2.4-GHz IEEE 802.15.4 and ZigBee Applications[S]. http://www.ti.com/lit/ds/symlink/cc2530.pdf.

[24] Dallas Semiconductor. DS18B20-PAR 1-Wire Parasite-Power Digital Thermometer[S]. https://datasheets.maximintegrated.com/en/ds/DS18B20-PAR.pdf.