李新路 張貫虹

（合肥學(xué)院，安徽 合肥 230601）

基于多級(jí)異構(gòu)網(wǎng)絡(luò)的無(wú)線傳感器網(wǎng)絡(luò)高效分簇路由算法

李新路 張貫虹

（合肥學(xué)院，安徽 合肥 230601）

在較大規(guī)模的無(wú)線傳感器網(wǎng)絡(luò)周期性數(shù)據(jù)采集應(yīng)用中，經(jīng)常會(huì)出現(xiàn)異構(gòu)網(wǎng)絡(luò)，LEACH等協(xié)議沒(méi)有考慮節(jié)點(diǎn)的異質(zhì)性。提出一種基于多級(jí)異構(gòu)網(wǎng)絡(luò)的高效路由分簇協(xié)議，考慮了節(jié)點(diǎn)的異質(zhì)性，為不同類型節(jié)點(diǎn)設(shè)置不同簇頭選舉概率及閾值函數(shù)，優(yōu)化簇頭選舉策略，較高初始能量和剩余能量的節(jié)點(diǎn)比低能量節(jié)點(diǎn)擁有更多的機(jī)會(huì)成為簇頭節(jié)點(diǎn)。實(shí)驗(yàn)結(jié)果表明，能夠高效地利用傳感器網(wǎng)絡(luò)采集數(shù)據(jù)，網(wǎng)絡(luò)負(fù)載總體均衡，并延長(zhǎng)網(wǎng)絡(luò)生存周期。

無(wú)線傳感器網(wǎng)絡(luò)；異構(gòu)網(wǎng)絡(luò)；能量高效

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSNs）由許多小型的，資源有限的傳感器節(jié)點(diǎn)以及基站組成的自組織、分布式網(wǎng)絡(luò)［1］。隨著傳感器系統(tǒng)，數(shù)據(jù)處理及無(wú)線通信的發(fā)展，無(wú)線傳感器網(wǎng)絡(luò)技術(shù)被廣泛的應(yīng)用于各類應(yīng)用，如環(huán)境監(jiān)測(cè)、軍事、化工檢測(cè)、醫(yī)療服務(wù)等行業(yè)［2］。由于傳感器節(jié)點(diǎn)的初始能量、帶寬、計(jì)算能力的限制，廣泛應(yīng)用于有線網(wǎng)絡(luò)或Ad Hoc網(wǎng)絡(luò)中的協(xié)議并不適用與WSNs。因而，設(shè)計(jì)出能量高效的路由協(xié)議，從而延長(zhǎng)網(wǎng)絡(luò)生命周期，成為WSNs研究的一個(gè)熱點(diǎn)問(wèn)題［1］［3］。

1 相關(guān)工作

在WSNs路由協(xié)議的設(shè)計(jì)中，分簇路由協(xié)議是較為經(jīng)典、高效的路由協(xié)議，它將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分成簇頭節(jié)點(diǎn)和成員節(jié)點(diǎn)兩類，首先使用特定的策略選舉簇頭，再根據(jù)距離等權(quán)函數(shù)形成簇，簇頭負(fù)責(zé)管理簇內(nèi)成員節(jié)點(diǎn)，執(zhí)行數(shù)據(jù)聚合函數(shù)，并傳輸數(shù)據(jù)到基站。LEACH（Low-Energy Adaptive Clustering Hierarchy）［4］是WSNs中最早提出的分簇路由協(xié)議，它是分簇路由協(xié)議的基礎(chǔ)。其基本思想是，通過(guò)等概率隨機(jī)周期性的選擇簇頭，再利用節(jié)點(diǎn)與簇頭之間的距離形成簇，將整個(gè)網(wǎng)絡(luò)的能耗均勻地分配到每一節(jié)點(diǎn)，從而達(dá)到降低能耗總量，延長(zhǎng)網(wǎng)絡(luò)生命周期的目的。但是LEACH沒(méi)有考慮到節(jié)點(diǎn)的剩余能量問(wèn)題，加速熱點(diǎn)問(wèn)題（hot spot problem）的形成。文獻(xiàn)［5］提出一種DCHS路由協(xié)議，DCHS改進(jìn)了簇頭選舉過(guò)程中的閾值函數(shù)，考慮了節(jié)點(diǎn)的剩余能量因素，使得節(jié)點(diǎn)能耗更加均勻，避免節(jié)點(diǎn)過(guò)早“死亡”。

HEED［6］是一種混合式能量高效的分布式分簇協(xié)議，它根據(jù)節(jié)點(diǎn)的剩余能量來(lái)選擇候選簇頭，并使用節(jié)點(diǎn)的度或鄰接節(jié)點(diǎn)距離作為內(nèi)部通信代價(jià)，以此來(lái)競(jìng)爭(zhēng)產(chǎn)生最終簇頭。實(shí)驗(yàn)證明，在一定的節(jié)點(diǎn)密度和簇內(nèi)簇間通信半徑下，HEED可以確定一個(gè)連通的分簇網(wǎng)絡(luò)，延長(zhǎng)網(wǎng)絡(luò)生命周期，并使得網(wǎng)絡(luò)更具有擴(kuò)展性。但是，HEED需要有限次迭代來(lái)選擇簇頭，其簇頭選舉開(kāi)銷比LEACH大了許多，在采用單跳模式下，其性能不如LEACH。

EECS［7］適用于周期性的數(shù)據(jù)收集應(yīng)用，它在簇頭選舉階段選取部分節(jié)點(diǎn)參加競(jìng)爭(zhēng)，采用無(wú)迭代過(guò)程的局部通信方式，選取剩余能量較多的節(jié)點(diǎn)擔(dān)任簇頭，進(jìn)一步，在簇的形成階段使用了一種簇頭負(fù)載均衡的方法。EECS協(xié)議控制消息開(kāi)銷小，形成的簇在空間上分布近似均勻，網(wǎng)絡(luò)能量利用率高。

這些基于LEACH的路由協(xié)議大都假定網(wǎng)絡(luò)節(jié)點(diǎn)是同質(zhì)的，即節(jié)點(diǎn)具有相同的初始能量和計(jì)算能力，然而在一些應(yīng)用中，如在現(xiàn)有網(wǎng)絡(luò)中增加部分新節(jié)點(diǎn)，網(wǎng)絡(luò)中會(huì)存在大量異質(zhì)節(jié)點(diǎn)。Mhatre等人在文獻(xiàn)［8］［9］中同時(shí)考量能耗成本及硬件成本作為整個(gè)網(wǎng)絡(luò)成本，較早地分析比較了WSNs中同質(zhì)網(wǎng)絡(luò)和異構(gòu)網(wǎng)絡(luò)的路由協(xié)議。UCS協(xié)議［10］針對(duì)異構(gòu)網(wǎng)絡(luò)，提出了非均勻分簇的路由策略，UCS假定所有高初始能量的節(jié)點(diǎn)位置已知，并指定其為簇頭節(jié)點(diǎn)，簇間通信采用多跳方式。為均衡能量負(fù)載，UCS利用文獻(xiàn)［8］提出的能耗模型，使網(wǎng)絡(luò)中的分簇大小不均勻分布，即距離基站較近的簇成員較少，從而達(dá)到整個(gè)網(wǎng)絡(luò)中簇頭能耗均勻的目的。SEP［11］協(xié)議考慮網(wǎng)絡(luò)中存在兩種初始能量不同的節(jié)點(diǎn)，通過(guò)在簇頭選舉概率和閾值函數(shù)中引入初始能量，使得具有較高能量的節(jié)點(diǎn)具有較大概率成為簇頭，延長(zhǎng)了傳感器網(wǎng)絡(luò)的穩(wěn)定周期①穩(wěn)定周期指從網(wǎng)絡(luò)開(kāi)始運(yùn)行直到第一個(gè)傳感器節(jié)點(diǎn)失效的時(shí)間間隔。在一些應(yīng)用中，當(dāng)一個(gè)傳感器節(jié)點(diǎn)失效后，網(wǎng)絡(luò)會(huì)變的很不穩(wěn)定。。

本文提出一種基于三級(jí)異構(gòu)網(wǎng)絡(luò)的分簇路由協(xié)議。LEACH及類LEACH分簇協(xié)議基于同構(gòu)網(wǎng)絡(luò)，在處理異構(gòu)網(wǎng)絡(luò)時(shí)沒(méi)有考慮節(jié)點(diǎn)的異質(zhì)性，從而使得節(jié)點(diǎn)的能耗分布不均勻。而UCS協(xié)議需要提前獲取異質(zhì)節(jié)點(diǎn)的位置，并且要求它們位置分布均勻，因而具有很大的局限性，不能滿足無(wú)線傳感器網(wǎng)絡(luò)的拓?fù)渥兓?。本文的協(xié)議區(qū)別于這兩類協(xié)議，在考慮網(wǎng)絡(luò)擴(kuò)展性和穩(wěn)定性的基礎(chǔ)上，使得節(jié)點(diǎn)能量負(fù)載均衡，從而延長(zhǎng)網(wǎng)絡(luò)的生命周期。

2 問(wèn)題描述和能量模型

2.1 問(wèn)題描述

本文提出的協(xié)議基于周期性數(shù)據(jù)收集應(yīng)用，如環(huán)境監(jiān)測(cè)等，我們假定：

（1）節(jié)點(diǎn)隨機(jī)均勻地分布在監(jiān)測(cè)區(qū)域，位置信息未知，基站位置固定；

（2）節(jié)點(diǎn)能量有限，網(wǎng)絡(luò)中存在異質(zhì)節(jié)點(diǎn)，基站能量不受限制；

（3）節(jié)點(diǎn)具有相似的處理及通信能力，可以擔(dān)任簇頭或普通節(jié)點(diǎn)；

（4）節(jié)點(diǎn)通信功率可控，可以根據(jù)距離來(lái)調(diào)節(jié)發(fā)射功率的大小，并可以根據(jù)接收信號(hào)的強(qiáng)度來(lái)計(jì)算節(jié)點(diǎn)之間的距離。

本文研究的無(wú)線傳感器網(wǎng)絡(luò)模型中有n個(gè)傳感器節(jié)點(diǎn)，一個(gè)基站。傳感器節(jié)點(diǎn)初始能量不均勻。同時(shí)，我們假定在網(wǎng)絡(luò)中有三種不同類型的節(jié)點(diǎn)：普通節(jié)點(diǎn)（normal nodes），中級(jí)節(jié)點(diǎn)（moderate nodes），高級(jí)節(jié)點(diǎn)（advance nodes）。

2.2 能量模型

本文采取與文獻(xiàn)［12］相同的能量模型。節(jié)點(diǎn)傳輸l比特的消息到距離為d的位置，消耗的能量由發(fā)射電路損耗和功率放大損耗兩部分組成，即

同時(shí)，為了接收比特的消息，需消耗能量為：

其中，Eelec表示發(fā)射電路損耗的能量。d0為閾值，當(dāng)傳輸距離d大于等于d0時(shí)，功率放大損耗采用多路徑衰減模型，損耗系數(shù)取4；反之，采用自由空間模型，損耗系數(shù)取2。此外，在數(shù)據(jù)融合時(shí)仍需消耗能量，用EDA表示融合單位比特?cái)?shù)據(jù)消耗的能量。

3 三級(jí)異構(gòu)網(wǎng)絡(luò)的分簇協(xié)議

3.1 LEACH分簇策略

LEACH協(xié)議通過(guò)輪（Round）來(lái)周期性的選擇簇頭。每輪中，每個(gè)節(jié)點(diǎn)都以概率Popt成為節(jié)點(diǎn)，建立簇時(shí)，每個(gè)節(jié)點(diǎn)產(chǎn)生0～1之間的隨機(jī)數(shù)，并于閾值函數(shù)T（s）比較，若小于T（s），則成為簇頭。

簇頭選擇結(jié)束后，每個(gè)簇頭通知其他非簇頭節(jié)點(diǎn)當(dāng)選消息，而非簇頭節(jié)點(diǎn)會(huì)依據(jù)與所有簇頭通信信號(hào)的強(qiáng)弱判斷加入哪個(gè)簇。在穩(wěn)定階段，簇頭收集來(lái)自簇內(nèi)的信息，進(jìn)行數(shù)據(jù)融合，傳輸至WSNs基站。

在上述閾值函數(shù)中，Popt指節(jié)點(diǎn)優(yōu)化簇頭概率，在n個(gè)節(jié)點(diǎn)中，簇頭優(yōu)化數(shù)量為kopt，根據(jù)文獻(xiàn)［12］，

由公式（4）（5）可知，Popt及kopt獨(dú)立于網(wǎng)絡(luò)的大小，并且只依賴于傳感器節(jié)點(diǎn)的數(shù)量。

LEACH協(xié)議基于同構(gòu)網(wǎng)絡(luò)，適用于節(jié)點(diǎn)同質(zhì)，且均勻分布的無(wú)線傳感器網(wǎng)絡(luò)。然而在應(yīng)用中，會(huì)出現(xiàn)大量異質(zhì)節(jié)點(diǎn)，如網(wǎng)絡(luò)運(yùn)行一段時(shí)間后，節(jié)點(diǎn)能量必定會(huì)分布不均勻，或者網(wǎng)絡(luò)加入了新節(jié)點(diǎn)。在我們討論的模型中，假定有三類異質(zhì)節(jié)點(diǎn)。

3.2 三級(jí)異構(gòu)網(wǎng)絡(luò)的分簇協(xié)議

文獻(xiàn)［10］中，UCS假定高級(jí)節(jié)點(diǎn)作為簇頭，因而需要高級(jí)節(jié)點(diǎn)位置已知，并且分布均勻。在本文討論的協(xié)議中，所有節(jié)點(diǎn)都有概率成為簇頭，即不需要提前獲得節(jié)點(diǎn)位置信息。直觀上，我們期望高級(jí)節(jié)點(diǎn)和中級(jí)節(jié)點(diǎn)成為簇頭的概率大于普通節(jié)點(diǎn)，從而使得整個(gè)網(wǎng)絡(luò)負(fù)載均衡，延長(zhǎng)網(wǎng)絡(luò)生命周期，為此，協(xié)議為不同類型節(jié)點(diǎn)設(shè)定不同的概率函數(shù)及閾值函數(shù)。

如前所述，網(wǎng)絡(luò)中存在三種類型節(jié)點(diǎn)，其初始能量及比例如下表：

表1 節(jié)點(diǎn)初始能量及數(shù)量

根據(jù)表1，三級(jí)異構(gòu)網(wǎng)絡(luò)的初始總能量可以描述成：

如前所述，優(yōu)化簇頭概率Popt只依賴于傳感器節(jié)點(diǎn)的數(shù)量，在三級(jí)異構(gòu)網(wǎng)絡(luò)中，相比較于LEACH協(xié)議中的同構(gòu)網(wǎng)絡(luò)，根據(jù)公式（6），可以理解成增加了α·m＋β·a個(gè)虛擬普通節(jié)點(diǎn)。為了使得網(wǎng)絡(luò)節(jié)點(diǎn)能量負(fù)載均衡，協(xié)議必須保證高級(jí)節(jié)點(diǎn)和中級(jí)節(jié)點(diǎn)當(dāng)選簇頭的概率大于普通節(jié)點(diǎn)，即滿足如下條件：

（4）每輪當(dāng)選的簇頭平均數(shù)量為n·Popt。

為此，給優(yōu)化簇頭概率Popt增加權(quán)值，普通節(jié)點(diǎn)，中級(jí)節(jié)點(diǎn)和高級(jí)節(jié)點(diǎn)的優(yōu)化簇頭概率計(jì)算公式分別如下：

4 仿真及性能評(píng)估

為驗(yàn)證協(xié)議的有效性，我們分別考慮如下性能參數(shù)：

網(wǎng)絡(luò)生命周期：不失一般性，本文分別從第一個(gè)節(jié)點(diǎn)死亡時(shí)間（First Node Dies，F(xiàn)ND），半數(shù)節(jié)點(diǎn)存活時(shí)間（Half of Nodes Alive，HNA）兩方面來(lái)驗(yàn)證網(wǎng)絡(luò)生命周期。

數(shù)據(jù)吞吐量：本文比較異構(gòu)網(wǎng)絡(luò)的數(shù)據(jù)吞吐量，分別衡量簇內(nèi)節(jié)點(diǎn)至簇頭及簇頭至基站的數(shù)據(jù)吞吐量。

每輪簇頭平均數(shù)：為驗(yàn)證協(xié)議的簇頭優(yōu)化概率及簇頭優(yōu)化數(shù)量，本文分析比較每輪當(dāng)選簇頭的平均數(shù)量。

本文采用與LEACH協(xié)議相似的實(shí)驗(yàn)參數(shù)，各項(xiàng)參數(shù)設(shè)置如表2所示。

表2 實(shí)驗(yàn)參數(shù)

根據(jù)表2中的參數(shù)，本文使用Matlab作為仿真工具，模擬實(shí)現(xiàn)了LEACH協(xié)議及本文所提出的新協(xié)議，并進(jìn)行性能比較分析。

4.1 網(wǎng)絡(luò)生命周期

圖1為網(wǎng)絡(luò)中采用LEACH協(xié)議及本文協(xié)議網(wǎng)絡(luò)存活節(jié)點(diǎn)數(shù)曲線圖，可以看到，采用本文協(xié)議的網(wǎng)絡(luò)穩(wěn)定周期明顯長(zhǎng)于LEACH協(xié)議，此外網(wǎng)絡(luò)的活躍時(shí)間也長(zhǎng)于LEACH協(xié)議。為了直觀的比較網(wǎng)絡(luò)生命周期，圖2列出了LEACH協(xié)議及本文所提出協(xié)議的生命周期對(duì)比圖，比較了第一個(gè)節(jié)點(diǎn)死亡時(shí)間（FND）及半數(shù)節(jié)點(diǎn)存活時(shí)間（HNA），在實(shí)際的應(yīng)用中，這兩中生命周期度量比最后一個(gè)節(jié)點(diǎn)死亡時(shí)間更加實(shí)際。由圖2可知，使用本文的協(xié)議，F(xiàn)ND和HNA均提高了約10%的性能。這表明本文的協(xié)議考慮到異構(gòu)節(jié)點(diǎn)的特性，并能夠更好的處理多級(jí)異構(gòu)網(wǎng)絡(luò)，延長(zhǎng)了網(wǎng)絡(luò)的生命周期。

圖1 生命周期對(duì)比圖

圖2 節(jié)點(diǎn)存活數(shù)曲線圖

4.2 網(wǎng)絡(luò)數(shù)據(jù)吞吐量

觀察圖3可知，采用本文協(xié)議的網(wǎng)絡(luò)數(shù)據(jù)吞吐量在生命周期內(nèi)明顯高于LEACH協(xié)議。WSNs數(shù)據(jù)吞吐量包括傳感器節(jié)點(diǎn)至簇頭數(shù)據(jù)吞吐量，簇頭至基站數(shù)據(jù)吞吐量。本文提出的協(xié)議基于周期性數(shù)據(jù)收集應(yīng)用，如環(huán)境監(jiān)測(cè)等，高數(shù)據(jù)吞吐量可以更加頻繁地采集數(shù)據(jù)，高效地利用傳感器網(wǎng)絡(luò)。

圖3 簇頭節(jié)點(diǎn)數(shù)分布

圖4 網(wǎng)絡(luò)數(shù)據(jù)吞吐量

4.3 每輪簇頭平均數(shù)

圖4分析了每一輪選舉產(chǎn)生的簇頭數(shù)量分布，由圖可知，約1000輪之前，LEACH協(xié)議及本文提出的協(xié)議每輪選舉的簇頭數(shù)均分布在10左右，根據(jù)文獻(xiàn)［12］及公式（4），簇頭優(yōu)化數(shù)量kopt只與網(wǎng)絡(luò)規(guī)模相關(guān)，而根據(jù)本文所采用的網(wǎng)絡(luò)參數(shù)，計(jì)算出kopt＝n·Popt=10，在1000輪之后，隨著部分節(jié)點(diǎn)能量逐漸耗盡，網(wǎng)絡(luò)規(guī)模逐步減少，每輪簇頭數(shù)量也隨之降低。由此可知，根據(jù)本文提出的簇頭選舉策略產(chǎn)生的簇頭數(shù)量與理論上所需的簇頭優(yōu)化數(shù)量基本一致，從而達(dá)到網(wǎng)絡(luò)負(fù)載總體均衡的目的。

5 總結(jié)

在較大規(guī)模的WSNs周期性數(shù)據(jù)采集應(yīng)用中，經(jīng)常會(huì)出現(xiàn)異構(gòu)網(wǎng)絡(luò)，或初始節(jié)點(diǎn)異質(zhì)，或運(yùn)行一段時(shí)間后產(chǎn)生異質(zhì)節(jié)點(diǎn)。本文提出一種多級(jí)異構(gòu)網(wǎng)絡(luò)的高效路由分簇協(xié)議。該協(xié)議考慮了節(jié)點(diǎn)的異質(zhì)性，為不同類型節(jié)點(diǎn)設(shè)置不同簇頭選舉概率及閾值函數(shù)，優(yōu)化簇頭選舉策略。實(shí)驗(yàn)結(jié)果表明，本文提出的協(xié)議，能夠高效地利用傳感器網(wǎng)絡(luò)采集數(shù)據(jù)，網(wǎng)絡(luò)負(fù)載總體均衡，并延長(zhǎng)網(wǎng)絡(luò)生存周期。

［1］沈波，張世永，鐘亦平.無(wú)線傳感器網(wǎng)絡(luò)分簇路由協(xié)議［J］.軟件學(xué)報(bào)，2006，（7）：1588-1600.

［2］Akkaya K，Younis M.A survey on routing protocols for wireless sensor networks［J］.Ad hoc networks，2005，（3）：325-349.

［3］Liu X.A survey on clustering routing protocols in wireless sensor networks［J］.Sensors，2012，（8）：11113-11153.

［4］Heinzelman W R，Chandrakasan A，Balakrishnan H.Energy-efficient communication protocol for wireless microsensor networks［C］.System sciences，2000.Proceedings of the 33rd annual Hawaii international conference on.IEEE，2000：10.

［5］Handy M J，Haase M，Timmermann D.Low energy adaptive clustering hierarchy with deterministic cluster-head selection［C］.Mobile and Wireless Communications Network，2002.4th International Workshop on.IEEE，2002：368-372.

［6］Younis O，F(xiàn)ahmy S.HEED：a hybrid，energy-efficient，distributed clustering approach for ad hoc sensor networks［J］.Mobile Computing，IEEE Transactions on，2004，（4）：366-379.

［7］陳貴海，李成法，葉懋，等.EECS：一種無(wú)線傳感器網(wǎng)絡(luò)中節(jié)能的聚類方案［J］.計(jì)算機(jī)科學(xué)與探索，2007，（2）.

［8］Mhatre V，Rosenberg C.Design guidelines for wireless sensor networks：communication，clustering and aggregation［J］.Ad Hoc Networks，2004，（1）：45-63.

［9］Mhatre V，Rosenberg C.Homogeneous vs heterogeneous clustered sensor networks：a comparative study［C］.Communications，2004 IEEE International Conference on.IEEE，2004：3646-3651.

［10］Soro S，Heinzelman W B.Prolonging the lifetime of wireless sensor networks via unequal clustering［C］.Parallel and Distributed Processing Symposium，2005.Proceedings.19th IEEE International.IEEE，2005：8.

［11］Smaragdakis G，Matta I，Bestavros A.SEP：A stable election protocol for clustered heterogeneous wireless sensor networks［R］.Boston University Computer Science Department，2004.

［12］Heinzelman W B，Chandrakasan A P，Balakrishnan H.An application-specific protocol architecture for wireless microsensor networks［J］.Wireless Communications，IEEE Transactions on，2002，（4）：660-670.

TP393

A

1672-2868（2015）03-0020-06

2015-03-15

合肥學(xué)院科研發(fā)展基金一般項(xiàng)目（項(xiàng)目編號(hào)：12KY07ZR）

李新路（1980-），男，安徽無(wú)為人。合肥學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系，講師。研究方向：無(wú)線傳感器網(wǎng)絡(luò)。

陳 侃