劉廣聰，陳平華，胡志斌

（廣東工業(yè)大學(xué)計算機(jī)學(xué)院，廣東廣州 510006）

0 引言

為了延長整個網(wǎng)絡(luò)的生存期，無線傳感器網(wǎng)絡(luò)的路由協(xié)議不僅關(guān)心單個節(jié)點(diǎn)的能量消耗，更要考慮整個網(wǎng)絡(luò)能量的均衡消耗。無線傳感器網(wǎng)絡(luò)的路由協(xié)議分為三大類:平面路由協(xié)議、層次化路由協(xié)議及地理位置路由協(xié)議。在平面路由協(xié)議中，靠近Sink的節(jié)點(diǎn)在執(zhí)行本身任務(wù)的同時還作為路由節(jié)點(diǎn)為遠(yuǎn)離Sink的節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)，能量會很快耗盡而引起網(wǎng)絡(luò)癱瘓，從能源有效性角度來看，平面路由協(xié)議并不適用于大規(guī)模密集部署的無線傳感器網(wǎng)絡(luò)［1，2］。層次化路由協(xié)議分簇算法的簇頭是隨機(jī)產(chǎn)生的，無法約束簇頭的位置，不能保證簇頭節(jié)點(diǎn)的均勻分布。如果節(jié)點(diǎn)密集處產(chǎn)生多個簇頭會形成簇頭冗余而造成能量的不合理開銷，并導(dǎo)致某些節(jié)點(diǎn)不屬于任何簇而處于孤立狀態(tài)，使節(jié)點(diǎn)的數(shù)據(jù)無法到達(dá)Sink節(jié)點(diǎn)［3］，低功耗自適應(yīng)集簇分層型［4］（low energy adaptive clustering hierarchy，LEACH）協(xié)議是一種典型的分層路由協(xié)議。文獻(xiàn)［5］中提出的PEGASIS協(xié)議是一種地理位置路由協(xié)議，它借鑒了LEACH中聚簇的思想，文獻(xiàn)［6］對這類協(xié)議給出類似于旅行商問題。

無線傳感器各個節(jié)點(diǎn)可能具有不同的特性和初始條件（即異構(gòu)節(jié)點(diǎn)），由于網(wǎng)絡(luò)中各節(jié)點(diǎn)的資源局限性、移動性及不穩(wěn)定性，要求路由協(xié)議具有可靠的鏈路發(fā)現(xiàn)和良好的路由節(jié)能能力。路由協(xié)議中各節(jié)點(diǎn)的能量保持與感知方法是路由協(xié)議設(shè)計的第一考慮要素，基于能量有效性的路由［7］利用剩余能量信息驗證能量的有效性。本文針對能量有效性路由的不足，采用節(jié)點(diǎn)信號強(qiáng)度與閾值感應(yīng)分?jǐn)?shù)建立路由鏈路，使路由信息驗證效率更高。

1 分布式數(shù)據(jù)處理模型

1．1 數(shù)據(jù)處理方式

常見的典型場景是具有N個節(jié)點(diǎn)的網(wǎng)絡(luò)，每一個節(jié)點(diǎn)可以收集到M個測量數(shù)據(jù)。如果需要這些測量值的平均值，存在3種方法獲取數(shù)據(jù)［8］:

1）節(jié)點(diǎn)將所有的數(shù)據(jù)發(fā)送給中央處理器，由中央處理器進(jìn)行計算。假設(shè)每次采樣的 bit數(shù)一定，則需要有O（MN）bit需要傳輸，其傳輸距離為固定長度，不受網(wǎng)絡(luò)屬性的影響，即為O（1）。

2）傳感器節(jié)點(diǎn)首先計算自己的平均值，然后再將平均值傳輸給中央處理器，由它計算最終的平均值。顯示需要O（N）bit需要傳輸，傳輸距離與第1種方法相同。

1．2 能耗分析

上述無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)處理方式可分為集中式數(shù)據(jù)處理與分布式數(shù)據(jù)處理。對于多跳通信方式，其計算能源消耗模型為ε（n）=c（n）×h（n）×e（n），其中，c（n）為傳輸?shù)腷it數(shù)目，h（n）為傳輸?shù)钠骄鴶?shù)，e（n）為每一跳傳輸1bit需要消耗的能源。

1）集中式算法的能耗計算

2）分布式算法的能耗計算

通過數(shù)據(jù)量和能耗分析比較可見，對于大規(guī)模無線傳感器節(jié)點(diǎn)的網(wǎng)絡(luò)，分布式算法比集中式算法整體上更具優(yōu)越性。

2 混合路由協(xié)議算法

本文采用分布式數(shù)據(jù)處理方式，在路由協(xié)議的構(gòu)建中，把網(wǎng)絡(luò)中的每個節(jié)點(diǎn)接收信號級值設(shè)定為若干個梯度值如下所示

每個梯度代表一個級別的節(jié)點(diǎn)通信強(qiáng)度值。

2．1 路由建立

考慮一個節(jié)點(diǎn)數(shù)為N的網(wǎng)絡(luò)，把整個網(wǎng)絡(luò)看成是一個無向圖G=（V，E），V表示圖中頂點(diǎn)的集合，E表示圖中邊的集合。N（i，j）表示節(jié)點(diǎn)N（i，j）的下一跳鄰居節(jié)點(diǎn)j的集合，其中，i，j∈V。w（u，v）表示邊（u，v）的權(quán)值（兩節(jié)點(diǎn)間的信號強(qiáng)度值SI），其中，邊w（u，v）∈E。Sink節(jié)點(diǎn)向周圍的傳感器節(jié)點(diǎn)發(fā)起通信請求時，Sink節(jié)點(diǎn)開始其路由過程。

構(gòu)造一個Sink節(jié)點(diǎn)到源節(jié)點(diǎn)s的路由。圖1中Sink節(jié)點(diǎn)用s表示，實(shí)線上的數(shù)字標(biāo)號表示該節(jié)點(diǎn)感知上一跳節(jié)點(diǎn)的信號強(qiáng)度（即SI值）。Sink節(jié)點(diǎn)首先廣播數(shù)據(jù)信息請求包（DRREQ）到鄰居節(jié)點(diǎn)集N（i，j）={i，j;i，j∈V}，在節(jié)點(diǎn)i，j收到DRREQ后，立即查看其Rid是否過期，如沒有則繼續(xù)查看所需信息是否自己所載信息，若是則給Sink節(jié)點(diǎn)數(shù)據(jù)應(yīng)答包（DRREP）;若Rid沒有過期且所需信息不是自己所載信息，則繼續(xù)向圖中的k，u節(jié)點(diǎn)路由，由于節(jié)點(diǎn)k，u并沒有攜帶Sink節(jié)點(diǎn)所需信息，繼續(xù)向其鄰居節(jié)點(diǎn)集N（u，ov）和N（k，vw）轉(zhuǎn)發(fā)，當(dāng)節(jié)點(diǎn)o，v，w收到 DRREQ 并檢測到自己都載有Sink節(jié)點(diǎn)所需的部分信息時，選取首個SI值最大的節(jié)點(diǎn)v作為簇頭節(jié)點(diǎn)并告知其鄰居節(jié)點(diǎn)o，p，w，q，用于v收集整合Sink節(jié)點(diǎn)所需的信息。當(dāng)節(jié)點(diǎn)o，p，w，q收到節(jié)點(diǎn)v的DRREQ信息時，將各自攜帶的部分信息按要求返回給簇頭節(jié)點(diǎn)v，節(jié)點(diǎn)v將這些信息進(jìn)行整合后按保存路由路徑（s，i，k，u，v）的反轉(zhuǎn)路徑返回 Sink 節(jié)點(diǎn)所需信息。

圖1 路由建立Fig 1 Routing setup

2．2 路由維護(hù)

本文的路由維護(hù)采用“最少修改原則”，如某鏈路出現(xiàn)了問題，該鏈路的始端節(jié)點(diǎn)廣播一個在線節(jié)點(diǎn)探尋信號ONCI，在該節(jié)點(diǎn)收到其鄰居節(jié)點(diǎn)返回的應(yīng)答信號PACI時，繼續(xù)轉(zhuǎn)發(fā)給Sink節(jié)點(diǎn)，查看返回給PACI的應(yīng)答節(jié)點(diǎn)是否在該鏈路的路由表中，若在，則將該節(jié)點(diǎn)加入到路由表的path中，修改從Sink節(jié)點(diǎn)到節(jié)點(diǎn)v的路由，更新路由表。

圖2詳細(xì)說明了該協(xié)議的路由維護(hù)。假設(shè)某時刻節(jié)點(diǎn)k已退出網(wǎng)絡(luò)（睡眠或關(guān)機(jī)等），此時Sink節(jié)點(diǎn)向節(jié)點(diǎn)v查詢相關(guān)信息，在Sink節(jié)點(diǎn)按路由表中的路徑發(fā)送試探信號后，由于節(jié)點(diǎn)k不能正常工作，鏈路R（i，k）和E（k，u）相繼中斷，使得節(jié)點(diǎn)v接收不到Sink節(jié)點(diǎn)的試探信號CI，也無法返回相關(guān)的應(yīng)答信號PACI。于是路由表中首先被中斷的鏈路E（i，k）的始端節(jié)點(diǎn)i，廣播一個在線節(jié)點(diǎn)探尋信號ONCI給其鄰居節(jié)點(diǎn)u，節(jié)點(diǎn)u在收到信號ONCI后，經(jīng)節(jié)點(diǎn)i返回給Sink節(jié)點(diǎn)一個應(yīng)答信號PACI，由“最少修改原則”將節(jié)點(diǎn)i加入路由表替換節(jié)點(diǎn)k，同時置SI值為最大進(jìn)行該鏈路的維護(hù)。

圖2 路由維護(hù)Fig 2 Routing maintenance

3 協(xié)議仿真與分析

比較 DECDC 協(xié)議［10］、文獻(xiàn)［11，12］中的協(xié)議，采用NS—2和Matlab軟件從簇頭的生成效率、成功數(shù)據(jù)交付率、網(wǎng)絡(luò)負(fù)載及平均能量消耗等四方面進(jìn)行評估與分析。

3．1 仿真環(huán)境

在仿真實(shí)驗中，傳感器節(jié)點(diǎn)被部署在一塊500 m×500 m的矩形目標(biāo)區(qū)域中，為了更好地與其他協(xié)議進(jìn)行比較和分析，仿真忽略由信號碰撞和無線信道干擾等隨機(jī)影響帶來的干擾。實(shí)驗參數(shù)設(shè)置如表1所示。

表1 仿真參數(shù)表Tab 1 Parameters of simulation

3．2 仿真結(jié)果與分析

從圖3可以看出:本協(xié)議的簇頭生成效率在節(jié)點(diǎn)密度為20以后明顯高于其他3種協(xié)議，原因是其他3種協(xié)議在整個網(wǎng)絡(luò)的通信中都是先成簇，再由簇頭負(fù)責(zé)其區(qū)域內(nèi)的數(shù)據(jù)采集、整合，然后將信息傳回給Sink節(jié)點(diǎn)。本文方法采用“盡力而為”和“不得已而為”的思想，采用Sink節(jié)點(diǎn)一次通信從某個節(jié)點(diǎn)獲取所需的全部信息，直接把信息返回給Sink節(jié)點(diǎn)，如果失敗，再以路由過程中SI值最大的節(jié)點(diǎn)動態(tài)自適應(yīng)生成簇頭進(jìn)行局部的信息采集和整理，最后將信息傳回Sink節(jié)點(diǎn)。

圖3 簇頭節(jié)點(diǎn)生成率Fig 3 Production rate of cluster head node

如圖4所示，正是本文這種“盡力而為”方式，在成功傳輸數(shù)據(jù)方面顯得更為有效。其他3種協(xié)議考慮到合理的簇頭分布，算法較為復(fù)雜，增加了網(wǎng)絡(luò)通信量。文獻(xiàn)［12］計算存儲空間大，但一旦路由建立數(shù)據(jù)交付率就很高，從圖4看出:在網(wǎng)絡(luò)存活節(jié)點(diǎn)達(dá)80之后文獻(xiàn)［12］高于其他3種協(xié)議，隨著節(jié)點(diǎn)數(shù)和無線通信量的增加，所有協(xié)議的數(shù)據(jù)傳遞率也逐漸下降。

圖4 成功報文交付率Fig 4 Successful packet delivery rate

圖5是4種協(xié)議的能耗比較。DECDC協(xié)議需時刻關(guān)注每節(jié)點(diǎn)到簇頭的距離和每節(jié)點(diǎn)的位置，這在節(jié)點(diǎn)邏輯位置不確定性的自組網(wǎng)中，需要消耗網(wǎng)絡(luò)大量的能量;文獻(xiàn)［11］采用基于網(wǎng)格算法來產(chǎn)生簇頭和路由，其計算量也相對較大;文獻(xiàn)［12］主要能耗是節(jié)點(diǎn)建立生成樹的計算和簇頭節(jié)點(diǎn)路由的消耗，相對前2種協(xié)議能耗小。從仿真結(jié)果可知，本文相對簡單的簇頭產(chǎn)生算法和節(jié)點(diǎn)狀態(tài)約束，使節(jié)點(diǎn)的休眠、關(guān)機(jī)和失效對通信沒有影響，可擴(kuò)展性好。

圖5 網(wǎng)絡(luò)能耗Fig 5 Energy consumption of network

4 結(jié)論

本文以剩余能量和節(jié)點(diǎn)間距離為參考因子的簇頭產(chǎn)生算法，把感知節(jié)點(diǎn)剩余能量強(qiáng)度和“盡力而為”的方法用于簇頭選擇和網(wǎng)絡(luò)數(shù)據(jù)查詢，避免了先成簇再路由的某些缺陷。仿真實(shí)驗結(jié)果表明:本協(xié)議的簇頭產(chǎn)生效率和數(shù)據(jù)交付成功率高，能有效降低節(jié)點(diǎn)能耗。

［1］ 崔 莉，鞠海玲，苗 勇，等．無線傳感器網(wǎng)絡(luò)研究進(jìn)展［J］．計算機(jī)研究與發(fā)展，2005，42（1）:163 －174．

［2］ 唐 勇，周明天，張 欣．無線傳感器網(wǎng)絡(luò)路由協(xié)議研究進(jìn)展［J］．軟件學(xué)報，2006，17（3）:410 －421．

［3］ Manjeshwar A，Agrawal D P．TEEN:a routing protocol for enhanced eficiency in wireless sensor networks［C］∥Proceedings of the 15th International Parallel and Distributed Processing Symposium，San Francisco，2001:2009 －2015．

［4］ Heinzelman W，Chandrakasan A，Balakrishnan H．Energy-efficient communication protocol for wireless microsensor networks［C］∥Proc of the 33rd Annual Hawaii Int’1 Conf on System Sciences，Maui:IEEE Computer Society，2000:3005 －3014．

［5］ Lindsey S，Raghavendra C S．PEGASIS:Power-efficient gathering in sensor information systems［C］∥Proceedings of the IEEE Aerospace Conference，New York:IEEE Press，2002:1125 －1130．

［6］ 蔡海濱，琚小明，曹奇英，等．多級能量異構(gòu)無線傳感器網(wǎng)絡(luò)的能量預(yù)測和可靠聚簇路由協(xié)議［J］．計算機(jī)學(xué)報，2009，32（12）:2393－2402．

［7］ Chatterjea S，Nieberg T．A distributed and self-organizing scheduling algorithm for energy-efficient data aggregation in wireless sensor network［J］．ACM Trans on Sensor，2008，4（4）:20—1—20—4．

［8］ Shakkottai S．Asymptotics of search strategies over a sensor network［J］．IEEE Trans on Automatic Control，2005，50（5）:594 －600．

［9］ Intanagonwiwat C，Govindan R，Estrin D．Directed diffusion:A scalable and robust communication paradigm for sensor networks［C］∥Proceedings of the 6th Annual ACM/IEEE International Conference on Mobile Computing and Networking，Boston，2000．

［10］ Jing Weipeng，Liu Yaqiu．DECDC:An energy-aware route protocol for wreless sensor networks［C］∥The 2nd Internation Symposium on Systems and Control in Aerospace and Astronautics，Shenzhen，2009:1－6．

［11］ Liu Shu，Zhuang Yanyan．Grid-based energy-aware routing in wireless sensor networks［J］．Journal of Southeast University:English Edition，2009，25（4）:445 －450．

［12］ Karthickraja N P，Sumathy V．A study of routing protocols and a hybrid routing protocol based on rapid spanning tree and cluster head routing in wireless sensor networks［C］∥International Conference on Wireless Communication and Senesor Computing，Chennai，2010:1 －6．