分區(qū)域的樹(shù)型多鏈的無(wú)線傳感器網(wǎng)絡(luò)路由算法

方旺盛，彭美平，胡中棟

（江西理工大學(xué) 信息工程學(xué)院，江西 贛州 341000）

無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）廣泛應(yīng)用于智慧農(nóng)業(yè)、環(huán)境監(jiān)控、戰(zhàn)場(chǎng)監(jiān)控和動(dòng)物跟蹤等方面，其由傳感模塊、存儲(chǔ)模塊、計(jì)算模塊、電源模塊組成。由于傳感器節(jié)點(diǎn)體積小，自身的計(jì)算、通信能力及存儲(chǔ)能量有限，WSN監(jiān)測(cè)的區(qū)域廣，部署的傳感器節(jié)點(diǎn)眾多，無(wú)法為大量傳感器節(jié)點(diǎn)更換電池等缺陷，使得有效節(jié)省全網(wǎng)節(jié)點(diǎn)能耗成為需要解決的重要問(wèn)題。路由協(xié)議是影響傳感器節(jié)點(diǎn)能耗的主要因素之一，也是提高無(wú)線傳感器網(wǎng)絡(luò)壽命的一個(gè)關(guān)鍵因素，其中分簇路由協(xié)議是路由協(xié)議的一類，因其節(jié)省能耗而被廣泛應(yīng)用。基于此，本文提出一種分區(qū)域的樹(shù)型多鏈的無(wú)線傳感器網(wǎng)絡(luò)路由算法。

1 經(jīng)典分簇路由算法分析

1.1 LEACH算法

LEACH算法將全網(wǎng)節(jié)點(diǎn)分成幾個(gè)簇，簇內(nèi)能進(jìn)行數(shù)據(jù)融合，可節(jié)省能耗，但簇頭節(jié)點(diǎn)需進(jìn)行數(shù)據(jù)計(jì)算，直接與sink節(jié)點(diǎn)通信等需消耗較多能量，會(huì)造成全網(wǎng)節(jié)點(diǎn)能量不均衡。因此LEACH算法會(huì)不斷進(jìn)行簇重構(gòu)、簇頭的重新選舉，這將會(huì)增加額外的能耗。

1.2 PEGASIS算法

PEGASIS（Power-Efficient GAthering in Sensor Information Systems）算法將全網(wǎng)節(jié)點(diǎn)形成一條長(zhǎng)鏈，鏈中相鄰兩節(jié)點(diǎn)間的距離相對(duì)較短，且數(shù)據(jù)傳輸時(shí)節(jié)點(diǎn)輪流當(dāng)選鏈頭與sink節(jié)點(diǎn)通信，不用簇的重構(gòu)、簇頭的重新選舉等，節(jié)省了開(kāi)銷。但PEGASIS算法仍然存在以下不足：第一，若無(wú)線傳感器網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)目較多，連接過(guò)程中形成一條長(zhǎng)鏈，會(huì)存在鏈的交叉、數(shù)據(jù)逆?zhèn)鞯葐?wèn)題，節(jié)點(diǎn)能量利用率不高；第二，在所構(gòu)建的鏈中，遠(yuǎn)距離的節(jié)點(diǎn)會(huì)引起過(guò)多的數(shù)據(jù)延時(shí)；第三，該協(xié)議所成鏈中只有一個(gè)鏈頭節(jié)點(diǎn)，使得鏈頭節(jié)點(diǎn)成為整個(gè)網(wǎng)絡(luò)的瓶頸。

1.3 COSEN算法

COSEN（A Chain Oriented Sensor Network）算法將整個(gè)全網(wǎng)所有節(jié)點(diǎn)形成的一條長(zhǎng)鏈拆成幾條短鏈，減少了鏈路長(zhǎng)度，每條分鏈同時(shí)收集數(shù)據(jù)進(jìn)行處理、融合，大大降低了網(wǎng)絡(luò)時(shí)延。當(dāng)網(wǎng)絡(luò)中某個(gè)節(jié)點(diǎn)死亡時(shí)，只對(duì)當(dāng)前分鏈和鏈頭節(jié)點(diǎn)形成的主鏈進(jìn)行維護(hù)，維護(hù)成本相對(duì)較低。但依然存在如下不足：第一，鏈內(nèi)存在交叉，易造成數(shù)據(jù)的回傳；第二，鏈間存在交叉，易造成算法的局部最優(yōu)。

2 本文算法

針對(duì)COSEN算法存在的缺陷，文獻(xiàn)[11]提出一種多級(jí)分層鏈路算法。該算法按照節(jié)點(diǎn)與基站的距離對(duì)全網(wǎng)節(jié)點(diǎn)分層，每層節(jié)點(diǎn)之間采用貪婪式的方法形成一條鏈。該算法雖然大幅降低了全網(wǎng)總能耗，但仍然存在缺陷：第一，若縱向的不在同層的2個(gè)節(jié)點(diǎn)相距較近，則無(wú)法連接到一條鏈，容易造成節(jié)點(diǎn)間跨度較大，增加能耗；第二，節(jié)點(diǎn)容易形成橫向跨度較大的長(zhǎng)鏈，從而造成節(jié)點(diǎn)的檢測(cè)數(shù)據(jù)差別較大，不利于數(shù)據(jù)融合；第三，若sink節(jié)點(diǎn)在網(wǎng)絡(luò)區(qū)域內(nèi)部，將形成半圓環(huán)的鏈或圓環(huán)的鏈，內(nèi)鏈長(zhǎng)度短，外鏈長(zhǎng)度長(zhǎng)，易造成節(jié)點(diǎn)能量消耗不均衡。鑒于以上討論，首先，本文算法將全網(wǎng)節(jié)點(diǎn)根據(jù)數(shù)據(jù)的相關(guān)性分為若干個(gè)長(zhǎng)條狀的區(qū)域，克服文獻(xiàn)[11]算法中縱向的不同層次的2個(gè)節(jié)點(diǎn)相距較近，而無(wú)法連接到一條鏈的情況；其次，本文算法區(qū)域中的節(jié)點(diǎn)根據(jù)它們之間的距離和角度形成樹(shù)型結(jié)構(gòu)的鏈，克服文獻(xiàn)[11]算法中橫向成鏈?zhǔn)拐麠l鏈較長(zhǎng)，從而節(jié)點(diǎn)的檢測(cè)數(shù)據(jù)差別較大，不利于數(shù)據(jù)融合的問(wèn)題；最后，本文算法將sink節(jié)點(diǎn)部署在網(wǎng)絡(luò)區(qū)域，彌補(bǔ)文獻(xiàn)[11]算法中sink節(jié)點(diǎn)部署在網(wǎng)絡(luò)區(qū)域內(nèi)能量消耗不均衡的情況。

2.1 算法設(shè)計(jì)思路

本文算法根據(jù)數(shù)據(jù)的相關(guān)性，將全網(wǎng)區(qū)域分成若干個(gè)長(zhǎng)條狀的區(qū)域，在每個(gè)區(qū)域中根據(jù)節(jié)點(diǎn)之間的距離和角度連接成一條鏈。成鏈過(guò)程中若產(chǎn)生交叉鏈，刪除兩交叉鏈中鏈較長(zhǎng)的那個(gè)，這樣會(huì)產(chǎn)生孤立節(jié)點(diǎn)，各個(gè)分區(qū)域內(nèi)的孤立節(jié)點(diǎn)找本區(qū)域中已經(jīng)成鏈的節(jié)點(diǎn)連接；區(qū)域外的孤立節(jié)點(diǎn)也找到已經(jīng)成鏈的節(jié)點(diǎn)連接，這樣就形成了分區(qū)域的樹(shù)型多鏈結(jié)構(gòu)。各分鏈鏈頭根據(jù)它們之間的距離和角度連接形成樹(shù)型主鏈，主鏈鏈頭與sink節(jié)點(diǎn)通信，或者各分鏈鏈頭直接與sink節(jié)點(diǎn)通信，即各分鏈鏈頭采用單跳和多跳相結(jié)合的方式與sink節(jié)點(diǎn)通信。

2.1.1 無(wú)線傳感器網(wǎng)絡(luò)分區(qū)

在無(wú)線傳感器網(wǎng)絡(luò)中，當(dāng)傳感器節(jié)點(diǎn)在網(wǎng)絡(luò)區(qū)域隨機(jī)部署完畢后，節(jié)點(diǎn)將檢測(cè)數(shù)據(jù)發(fā)給鄰居節(jié)點(diǎn)，鄰居節(jié)點(diǎn)根據(jù)收到的數(shù)據(jù)將從離sink節(jié)點(diǎn)近的節(jié)點(diǎn)開(kāi)始依次向外將全網(wǎng)區(qū)域分成若干區(qū)域。在分區(qū)域過(guò)程中判斷該區(qū)域是否為長(zhǎng)條狀區(qū)域，即區(qū)域的長(zhǎng)寬是否在上下閾值之間。若區(qū)域的長(zhǎng)寬低于上下閾值，則區(qū)域中加入新的節(jié)點(diǎn)；若區(qū)域的長(zhǎng)寬超過(guò)上下閾值，則區(qū)域中去掉加入的節(jié)點(diǎn)或者更換節(jié)點(diǎn)加入，直到整個(gè)分區(qū)域在上下閾值之間。從離sink節(jié)點(diǎn)近的節(jié)點(diǎn)開(kāi)始依次向外劃分，直到所有區(qū)域劃分為長(zhǎng)條狀區(qū)域。對(duì)于網(wǎng)絡(luò)邊緣的區(qū)域，節(jié)點(diǎn)往往比較稀疏，網(wǎng)絡(luò)區(qū)域可以不滿足設(shè)定閾值，只要節(jié)點(diǎn)能量消耗小即可。分區(qū)域流程如圖1所示。

圖1 分區(qū)域流程圖

分區(qū)過(guò)程的偽代碼如下：

2.1.2 區(qū)域內(nèi)的節(jié)點(diǎn)連接成鏈

將整個(gè)網(wǎng)絡(luò)區(qū)域分成幾個(gè)長(zhǎng)條狀的區(qū)域后，在每個(gè)子區(qū)域中根據(jù)節(jié)點(diǎn)之間的距離和角度將節(jié)點(diǎn)連接成一條鏈，具體成鏈過(guò)程如下：

如圖2所示，在一個(gè)分區(qū)域中，節(jié)點(diǎn)為該區(qū)域的終節(jié)點(diǎn)，節(jié)點(diǎn)為將要成鏈的節(jié)點(diǎn)，以節(jié)點(diǎn)為例來(lái)說(shuō)明具體成鏈的過(guò)程。節(jié)點(diǎn)的下一跳節(jié)點(diǎn)從它的相鄰節(jié)點(diǎn)中選取，有，，，，，共6個(gè)節(jié)點(diǎn)。選擇哪個(gè)節(jié)點(diǎn)作為節(jié)點(diǎn)的下一跳節(jié)點(diǎn)，取決于下式：

式中：d 為節(jié)點(diǎn)到節(jié)點(diǎn)的下一跳節(jié)點(diǎn)的距離；為節(jié)點(diǎn)到節(jié)點(diǎn)連線與節(jié)點(diǎn)到下一跳節(jié)點(diǎn)連線的夾角。將，，，，，共6個(gè)節(jié)點(diǎn)代入式（1），顯然，W ＜W ＜W ＜W ＜W =W =，選擇使W 值最小的節(jié)點(diǎn)為下一跳節(jié)點(diǎn)。然后依據(jù)式（1），用節(jié)點(diǎn)和它下一跳節(jié)點(diǎn)之間的距離和角度兩個(gè)因素相結(jié)合的方式將節(jié)點(diǎn)連接起來(lái)形成一條鏈，若成鏈過(guò)程中產(chǎn)生交叉鏈，刪除兩交叉鏈中鏈較長(zhǎng)的那個(gè)，這樣可形成分區(qū)域的主干鏈。

區(qū)域中的節(jié)點(diǎn)形成主干鏈的過(guò)程中，會(huì)產(chǎn)生如圖2中，，，，這樣的孤立節(jié)點(diǎn)。這些孤立節(jié)點(diǎn)按照式（1）找到本區(qū)域中使它們的值最小的下一跳節(jié)點(diǎn)連接。

圖2 區(qū)域內(nèi)節(jié)點(diǎn)連接成鏈

圖3中節(jié)點(diǎn)、節(jié)點(diǎn)、節(jié)點(diǎn)分別與已成鏈節(jié)點(diǎn)、節(jié)點(diǎn)、節(jié)點(diǎn)建立連接。

若根據(jù)式（1），使孤立節(jié)點(diǎn)最小值的下一跳節(jié)點(diǎn)不在主干鏈上，那么離已成鏈節(jié)點(diǎn)近的孤立節(jié)點(diǎn)先根據(jù)式（1）找到使孤立節(jié)點(diǎn)最小值的下一跳節(jié)點(diǎn)，并計(jì)算值；然后找到孤立節(jié)點(diǎn)的下一跳在主干鏈上的節(jié)點(diǎn)，計(jì)算它們的值。最小的值記為；最小的值記為；最后比較和的值，找到值最小的下一跳節(jié)點(diǎn)連接。值計(jì)算公式如下：

式中：d 為節(jié)點(diǎn)到節(jié)點(diǎn)的下一跳節(jié)點(diǎn)的距離；為節(jié)點(diǎn)到節(jié)點(diǎn)連線與節(jié)點(diǎn)到下一跳節(jié)點(diǎn)連線的夾角；為節(jié)點(diǎn)要連的下一跳節(jié)點(diǎn)所在分支鏈中的節(jié)點(diǎn)個(gè)數(shù)。若孤立節(jié)點(diǎn)，使它的值最小的下一跳節(jié)點(diǎn)為節(jié)點(diǎn)，節(jié)點(diǎn)的最小值的下一跳節(jié)點(diǎn)為節(jié)點(diǎn)，節(jié)點(diǎn)和節(jié)點(diǎn)都不在主干鏈中，節(jié)點(diǎn)離已成鏈節(jié)點(diǎn)較近，為分支鏈中的第一個(gè)節(jié)點(diǎn)，且已連接到鏈中；接著節(jié)點(diǎn)離已成鏈節(jié)點(diǎn)較近，根據(jù)式（2）找到使節(jié)點(diǎn)最小值的下一跳節(jié)點(diǎn)為節(jié)點(diǎn)，并計(jì)算F 的值；然后在節(jié)點(diǎn)的鄰居節(jié)點(diǎn)中找到下一跳在主干鏈上的節(jié)點(diǎn)，節(jié)點(diǎn)是節(jié)點(diǎn)下一跳在主干鏈上的節(jié)點(diǎn)中值最小節(jié)點(diǎn)，并計(jì)算W 的值。因?yàn)楣?jié)點(diǎn)F ＜W ，所以節(jié)點(diǎn)的下一跳節(jié)點(diǎn)為節(jié)點(diǎn)。同理，因?yàn)?span id="j5i0abt0b" class="emphasis_italic">W ＜F ，所以節(jié)點(diǎn)的下一跳節(jié)點(diǎn)為節(jié)點(diǎn)。區(qū)域中的孤立節(jié)點(diǎn)的鏈接如圖3所示。

圖3 區(qū)域內(nèi)孤立節(jié)點(diǎn)連接成鏈

2.1.3 區(qū)域外的節(jié)點(diǎn)連接成鏈

分區(qū)域外的孤立節(jié)點(diǎn)分別找使它們的值最小的下一跳已成鏈節(jié)點(diǎn)連接成鏈，如圖4中的節(jié)點(diǎn)、節(jié)點(diǎn)分別與已成鏈節(jié)點(diǎn)、節(jié)點(diǎn)連接。

圖4 區(qū)域外的節(jié)點(diǎn)連接成鏈

2.1.4 鏈頭節(jié)點(diǎn)的選舉及通信

在形成的各條分鏈中，鏈中節(jié)點(diǎn)輪流當(dāng)鏈頭，輪流的原則遵循相鄰鏈的鏈頭之間的距離盡可能小。

各分鏈選出鏈頭節(jié)點(diǎn)后，分鏈鏈頭與sink節(jié)點(diǎn)的通信采用文獻(xiàn)[13]中單跳和多跳相結(jié)合的通信方式。單跳時(shí)遠(yuǎn)處分鏈的鏈頭節(jié)點(diǎn)耗能大，多跳時(shí)近處分鏈的鏈頭節(jié)點(diǎn)耗能大。節(jié)點(diǎn)總的數(shù)據(jù)通信時(shí)間為，在·時(shí)間內(nèi)，分鏈鏈頭以單跳的方式與sink節(jié)點(diǎn)通信；在·( 1-)的時(shí)間內(nèi)，分鏈鏈頭以多跳的方式與sink節(jié)點(diǎn)通信。

分鏈鏈頭的多跳傳輸需要成鏈，成鏈的規(guī)則和各分區(qū)域節(jié)點(diǎn)的成鏈規(guī)則一樣，即根據(jù)鏈頭節(jié)點(diǎn)之間的距離和角度形成樹(shù)型主鏈。樹(shù)型主鏈找到離sink節(jié)點(diǎn)最近的節(jié)點(diǎn)充當(dāng)主鏈鏈頭與sink節(jié)點(diǎn)通信。全網(wǎng)節(jié)點(diǎn)具體成鏈情況如圖5所示。

圖5 全網(wǎng)節(jié)點(diǎn)所成鏈路

2.2 算法偽代碼

3 算法仿真與分析

本文設(shè)定的實(shí)驗(yàn)區(qū)域?yàn)?00 m×100 m，區(qū)域中部署100個(gè)傳感器節(jié)點(diǎn)?？紤]到數(shù)據(jù)的相關(guān)性、鏈的長(zhǎng)度、網(wǎng)絡(luò)整體的時(shí)延及能耗，將整個(gè)傳感器網(wǎng)絡(luò)區(qū)域分為6個(gè)長(zhǎng)條狀的區(qū)域，長(zhǎng)條狀區(qū)域的長(zhǎng)、寬的上閾值分別為100 m，20 m，下閾值為35 m，5 m。

本文采用Matlab仿真實(shí)驗(yàn)，并與在本區(qū)域中利用PEGASIS算法、COSEN算法、文獻(xiàn)[11]的MSLR（Multistage Stratified Link Routing）算法進(jìn)行仿真實(shí)驗(yàn)的結(jié)果進(jìn)行對(duì)比，從節(jié)點(diǎn)的成鏈情況、節(jié)點(diǎn)死亡數(shù)目、網(wǎng)絡(luò)能量消耗和時(shí)延四個(gè)方面進(jìn)行分析評(píng)估。算法的仿真參數(shù)如表1所示。

表1 仿真參數(shù)

3.1 節(jié)點(diǎn)成鏈情況

圖6中的4幅仿真圖分別為PEGASIS算法、COSEN算法、MSLR算法和本文算法形成的仿真圖。將四種算法成鏈情況做對(duì)比可以看出：前兩種算法形成的鏈存在明顯的交叉，整體較亂；而MSLR算法雖然比前兩種算法有條理，但依然存在鏈間交叉和某些鏈較長(zhǎng)的問(wèn)題；本文算法形成的樹(shù)型結(jié)構(gòu)有明顯的條理且無(wú)交叉，相比PEGASIS算法形成的鏈較短，相比COSEN算法和MSLR算法形成的鏈無(wú)交叉，可避免數(shù)據(jù)的回傳。

圖6 各算法鏈?zhǔn)綀D對(duì)比

3.2 能耗分析

本文以網(wǎng)絡(luò)區(qū)域中全部節(jié)點(diǎn)到sink節(jié)點(diǎn)的一次數(shù)據(jù)傳輸為一個(gè)周期，對(duì)比四種算法在工作過(guò)程中節(jié)點(diǎn)的死亡數(shù)目和全網(wǎng)能量消耗情況，如圖7、圖8所示。從圖7可以看出，本文算法比前三種算法的首個(gè)節(jié)點(diǎn)的死亡數(shù)量和全網(wǎng)所有節(jié)點(diǎn)的死亡數(shù)量都有所延長(zhǎng)。本文算法的首個(gè)節(jié)點(diǎn)死亡的輪數(shù)大約在660輪，比PEGASIS算法、COSEN算法、MSLR算法的首個(gè)節(jié)點(diǎn)死亡的輪數(shù)分別延長(zhǎng)了大約260輪、140輪、100輪。

圖7 每輪死亡節(jié)點(diǎn)數(shù)對(duì)比

本文算法的全網(wǎng)全部節(jié)點(diǎn)死亡的輪數(shù)大約在920輪，比PEGASIS算法、COSEN算法、MSLR算法的全網(wǎng)全部節(jié)點(diǎn)死亡的輪數(shù)分別延長(zhǎng)了大約180輪、90輪、70輪，本文算法生命周期有所延長(zhǎng)。

從圖8的全網(wǎng)節(jié)點(diǎn)能量消耗對(duì)比的仿真圖可以看出，PEGASIS算法在740輪時(shí)全網(wǎng)能量基本消耗完畢，COSEN算法全網(wǎng)能量基本消耗完在830輪，MSLR算法在850輪時(shí)全網(wǎng)能量基本消耗完畢，本文的算法全網(wǎng)能量基本消耗完畢在920輪，在同一周期內(nèi)比PEGASIS算法、COSEN算法和MSLR算法的全網(wǎng)節(jié)點(diǎn)能量消耗都小。

圖8 全網(wǎng)節(jié)點(diǎn)能量消耗對(duì)比

3.3 時(shí)延分析

圖9是四種算法從節(jié)點(diǎn)開(kāi)始工作到第一個(gè)節(jié)點(diǎn)死亡時(shí)間內(nèi)的時(shí)延情況對(duì)比仿真圖。

圖9 節(jié)點(diǎn)時(shí)延情況對(duì)比

從圖9可以看出，本文算法時(shí)延最短，PEGASIS算法時(shí)延最長(zhǎng)，并且比另外兩種算法時(shí)延大得多。原因在于PEGASIS算法全網(wǎng)形成一條鏈，只有一個(gè)鏈頭與sink節(jié)點(diǎn)通信，所以時(shí)延較大；COSEN算法和MSLR算法形成多條分鏈，分鏈節(jié)點(diǎn)同時(shí)傳輸數(shù)據(jù)，減少了時(shí)延。而本文算法將全網(wǎng)節(jié)點(diǎn)也分為幾條短鏈，鏈中節(jié)點(diǎn)可同時(shí)傳輸數(shù)據(jù)，且短鏈?zhǔn)菢?shù)型結(jié)構(gòu)，相鄰兩節(jié)點(diǎn)相距較小，鏈中無(wú)交叉?zhèn)鬟f數(shù)據(jù)，所以比其他兩種算法的時(shí)延都小。

4 結(jié) 語(yǔ)

本文通過(guò)將無(wú)線傳感器網(wǎng)絡(luò)分成長(zhǎng)條狀的區(qū)域，區(qū)域中的節(jié)點(diǎn)根據(jù)距離和角度連接成鏈，減少了節(jié)點(diǎn)之間的距離，使全網(wǎng)節(jié)點(diǎn)數(shù)據(jù)傳輸時(shí)延減??；并且區(qū)域中的節(jié)點(diǎn)之間無(wú)交叉，避免了數(shù)據(jù)的逆?zhèn)鬟f，減少了網(wǎng)絡(luò)整體能耗。從整體上來(lái)看，節(jié)點(diǎn)傳輸數(shù)據(jù)時(shí)延縮短，節(jié)點(diǎn)的生命周期有所提升。

注：本文通訊作者為彭美平。