一種基于AHP和FIS的WSN路由算法

周文康，王行甫

（1.中國(guó)科學(xué)技術(shù)大學(xué) 網(wǎng)絡(luò)空間安全學(xué)院，合肥 230022；2.中國(guó)科學(xué)技術(shù)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，合肥 230022）

0 概述

無線傳感器網(wǎng)絡(luò)（Wireless Sensor Network，WSN）［1］由許多能量受限的傳感器節(jié)點(diǎn)構(gòu)成，一般用來完成環(huán)境感知和數(shù)據(jù)收集任務(wù)。傳感器節(jié)點(diǎn)能量有限且難以維護(hù)，通常部署在水下、森林深處、火山口等人類無法到達(dá)的地方。因此，能量對(duì)于傳感器節(jié)點(diǎn)而言至關(guān)重要，能量的使用效率直接決定了WSN 的生命周期。

為了降低傳感器節(jié)點(diǎn)的能量消耗，WSN 中通常引入醒睡機(jī)制，即節(jié)點(diǎn)周期性地在醒睡模式之間進(jìn)行切換［2］，只有當(dāng)節(jié)點(diǎn)處于醒模式下才可正常通信，而處于睡眠模式的節(jié)點(diǎn)則無法與鄰居節(jié)點(diǎn)進(jìn)行通信，但是會(huì)大幅降低能量的消耗。

WSN 中通常有2 種介質(zhì)訪問控制（Medium Access Control，MAC）協(xié)議，即同步MAC 協(xié)議和異步MAC 協(xié)議。在同步MAC 協(xié)議中，所有節(jié)點(diǎn)都在同一時(shí)刻醒來，發(fā)送節(jié)點(diǎn)可以直接將數(shù)據(jù)發(fā)送給接收節(jié)點(diǎn)而不需要等待；在異步MAC 協(xié)議中，發(fā)送節(jié)點(diǎn)往往會(huì)花費(fèi)很長(zhǎng)時(shí)間等待接收節(jié)點(diǎn)醒來然后才能發(fā)送數(shù)據(jù)，這將大幅增加發(fā)送節(jié)點(diǎn)的等待時(shí)延。

為了解決異步WSN 中發(fā)送節(jié)點(diǎn)等待時(shí)延過長(zhǎng)的問題，節(jié)點(diǎn)一般從鄰居節(jié)點(diǎn)中選擇多個(gè)節(jié)點(diǎn)作為候選轉(zhuǎn)發(fā)節(jié)點(diǎn)。當(dāng)發(fā)送節(jié)點(diǎn)有數(shù)據(jù)要進(jìn)行發(fā)送時(shí)，從醒來的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)中選擇一個(gè)作為接收節(jié)點(diǎn)，這將減少發(fā)送節(jié)點(diǎn)的等待時(shí)延。這種選擇多接收節(jié)點(diǎn)構(gòu)成轉(zhuǎn)發(fā)節(jié)點(diǎn)集的方法的時(shí)延性能遠(yuǎn)優(yōu)于單接收節(jié)點(diǎn)方法，但是其對(duì)路由算法也提出了更高的要求，如果處理不當(dāng)，不僅不會(huì)取得性能上的提升，還會(huì)造成更多的能量消耗，原因是：存在候選節(jié)點(diǎn)集大小問題，當(dāng)候選節(jié)點(diǎn)集過小時(shí)，將不能很好地減少發(fā)送節(jié)點(diǎn)的等待時(shí)延，當(dāng)候選節(jié)點(diǎn)集過大時(shí)，會(huì)提高多接收節(jié)點(diǎn)出現(xiàn)的概率，即多個(gè)候選節(jié)點(diǎn)同時(shí)醒來，這將產(chǎn)生過多的冗余數(shù)據(jù)包從而消耗節(jié)點(diǎn)的能量；存在候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的選擇問題，由于評(píng)估選擇算法的不合理導(dǎo)致一些不好的節(jié)點(diǎn)被選擇加入至候選轉(zhuǎn)發(fā)集中，當(dāng)數(shù)據(jù)包經(jīng)過這些節(jié)點(diǎn)轉(zhuǎn)發(fā)時(shí)會(huì)使得網(wǎng)絡(luò)性能下降，例如，數(shù)據(jù)包通過離sink 位置較遠(yuǎn)的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)會(huì)導(dǎo)致路由路徑變長(zhǎng)，端到端延遲和轉(zhuǎn)發(fā)數(shù)據(jù)包所需能耗提升；數(shù)據(jù)包通過低能量節(jié)點(diǎn)轉(zhuǎn)發(fā)會(huì)導(dǎo)致該節(jié)點(diǎn)過早地因能量耗盡而無法繼續(xù)工作等。

由以上分析可知，候選轉(zhuǎn)發(fā)節(jié)點(diǎn)的評(píng)估與選擇對(duì)網(wǎng)絡(luò)性能影響較大。為了更好地對(duì)節(jié)點(diǎn)進(jìn)行評(píng)估，選擇更合理的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，本文基于層次分析法（Analytic Hierarchy Process，AHP）和模糊推理系統(tǒng)（Fuzzy Inference System，F(xiàn)IS），提出一種DAF（Dynamic evaluation algorithm based on AHP and FIS）算法，該算法在網(wǎng)絡(luò)運(yùn)行的過程中根據(jù)節(jié)點(diǎn)信息使用FIS 動(dòng)態(tài)構(gòu)建AHP 中的成對(duì)比較矩陣，從而實(shí)現(xiàn)對(duì)鄰居節(jié)點(diǎn)的動(dòng)態(tài)評(píng)分。

1 相關(guān)工作

為了降低傳感器節(jié)點(diǎn)的能耗、提高WSN 的生命周期，研究人員提出很多MAC 層和路由層協(xié)議。

文獻(xiàn)［3］提出一個(gè)異步MAC 協(xié)議B-MAC，當(dāng)發(fā)送節(jié)點(diǎn)有數(shù)據(jù)包要發(fā)送時(shí)，會(huì)先發(fā)送一個(gè)前導(dǎo)碼包給鄰居節(jié)點(diǎn)，詢問它們的狀態(tài)信息，處于醒模式下的鄰居節(jié)點(diǎn)會(huì)接收該前導(dǎo)碼包并發(fā)回一個(gè)ACK 確認(rèn)包，發(fā)送節(jié)點(diǎn)在接收到這些ACK 之后會(huì)從中選擇一個(gè)節(jié)點(diǎn)作為接收節(jié)點(diǎn)并將數(shù)據(jù)包轉(zhuǎn)發(fā)給該節(jié)點(diǎn)，如果沒有鄰居節(jié)點(diǎn)醒來，即發(fā)送節(jié)點(diǎn)接收不到ACK，則會(huì)不間斷地發(fā)送前導(dǎo)碼包。文獻(xiàn)［4］提出另一種異步MAC 協(xié)議X-MAC，相較于B-MAC，X-MAC 發(fā)送的前導(dǎo)碼包較短。文獻(xiàn)［5］提出BoX-MAC，該協(xié)議通過共享物理層和數(shù)據(jù)鏈路層的信息來減少節(jié)點(diǎn)的能量消耗從而提高網(wǎng)絡(luò)性能。

文獻(xiàn)［6］基于ETX（Expected Transmission Count）提出一種路由參數(shù)EDC（Expected Duty Cycled wake-ups），其表示到達(dá)sink 節(jié)點(diǎn)所需要的平均醒睡周期數(shù)，EDC越小的節(jié)點(diǎn)表示離sink 越近，且只有當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)EDC 才會(huì)改變。發(fā)送節(jié)點(diǎn)會(huì)選擇EDC 較小的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，因此，這些節(jié)點(diǎn)往往會(huì)因?yàn)榻邮者^多的數(shù)據(jù)包而導(dǎo)致能量消耗比其他節(jié)點(diǎn)更快。

文獻(xiàn)［7］在EDC 的基礎(chǔ)上考慮節(jié)點(diǎn)的剩余能量，剩余能量越高的節(jié)點(diǎn)越有可能被選擇作為接收節(jié)點(diǎn)，EDC 較小的節(jié)點(diǎn)會(huì)因?yàn)槠涫Ｓ嗄芰枯^低而被選擇作為接收節(jié)點(diǎn)的優(yōu)先級(jí)降低，因此，其能均衡網(wǎng)絡(luò)負(fù)載并提高網(wǎng)絡(luò)生命周期。

在文獻(xiàn)［8］中，數(shù)據(jù)包被節(jié)點(diǎn)接收后不會(huì)被立即轉(zhuǎn)發(fā)，若在短時(shí)間內(nèi)有新的數(shù)據(jù)包被接收，則該節(jié)點(diǎn)會(huì)將這些數(shù)據(jù)包進(jìn)行融合之后再發(fā)送，通過減少發(fā)送次數(shù)來節(jié)省能耗，但是這對(duì)數(shù)據(jù)融合算法提出了較高的要求，當(dāng)網(wǎng)絡(luò)數(shù)據(jù)傳輸率較低時(shí)，往往在網(wǎng)絡(luò)性能上表現(xiàn)不佳。

文獻(xiàn)［9］提出一種自適應(yīng)路由協(xié)議AOR（Adaptive Opportunistic Routing），其采用分區(qū)方案來提高網(wǎng)絡(luò)的吞吐量，即根據(jù)節(jié)點(diǎn)和匯聚節(jié)點(diǎn)之間的位置關(guān)系，將整個(gè)網(wǎng)絡(luò)分成不同的區(qū)域，每個(gè)區(qū)域擁有不同的優(yōu)先級(jí)。但是，由于區(qū)域劃分的計(jì)算量較大且無法實(shí)現(xiàn)動(dòng)態(tài)計(jì)算，因此在網(wǎng)絡(luò)拓?fù)浒l(fā)生動(dòng)態(tài)變化時(shí)，無法準(zhǔn)確地將不同位置的節(jié)點(diǎn)劃入不同的區(qū)域中，從而導(dǎo)致網(wǎng)絡(luò)性能下降。

文獻(xiàn)［10］采用和AOR 類似的分區(qū)思想，提出一種新的路由協(xié)議算法OR-AHaD（an Opportunistic Routing algorithm withAdaptive Harvesting-aware Duty Cycling）。該算法可根據(jù)節(jié)點(diǎn)的位置信息進(jìn)行區(qū)域劃分，同時(shí)結(jié)合節(jié)點(diǎn)自身剩余能量調(diào)整休眠周期的占空比（Duty Cycle），綜合各因素后確定不同節(jié)點(diǎn)的優(yōu)先級(jí)和候選節(jié)點(diǎn)集。但是，該算法對(duì)數(shù)據(jù)傳輸所需要的代價(jià)評(píng)估往往不夠準(zhǔn)確，導(dǎo)致其在丟包率上性能表現(xiàn)相對(duì)較差。

文獻(xiàn)［11］提出方向分布、傳輸距離分布、垂直距離分布、剩余能量分布這4 種分布，通過參數(shù)控制4 種分布的權(quán)重，最終計(jì)算出每個(gè)節(jié)點(diǎn)的得分。同時(shí)，為每個(gè)節(jié)點(diǎn)定義一個(gè)矩形范圍，稱為CZ（Candidates Zone），只有CZ 中的節(jié)點(diǎn)才可被選擇作為轉(zhuǎn)發(fā)節(jié)點(diǎn)。但是，該網(wǎng)絡(luò)性能在很大程度上受到參數(shù)的影響，在網(wǎng)絡(luò)運(yùn)行過程中，參數(shù)不可動(dòng)態(tài)改變，因此，很難在網(wǎng)絡(luò)運(yùn)行之前確定合理的分布權(quán)重參數(shù)。

文獻(xiàn)［12］為了提高WSN 路由算法的靈活性，提出一種新的路由算法FRCA，在該算法中，節(jié)點(diǎn)的轉(zhuǎn)發(fā)概率取決于多個(gè)部分，包括影響網(wǎng)絡(luò)性能的物理量、基本的數(shù)學(xué)函數(shù)以及路由參數(shù)，通過調(diào)整各個(gè)部分的參數(shù)權(quán)重，最終計(jì)算出節(jié)點(diǎn)的路由度量，在節(jié)點(diǎn)轉(zhuǎn)發(fā)數(shù)據(jù)包時(shí)用該度量來進(jìn)行接收節(jié)點(diǎn)的選擇。但是，針對(duì)不同的網(wǎng)絡(luò)應(yīng)用來調(diào)整一組合適的路由參數(shù)非常困難，且當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)該算法不能在運(yùn)行過程中進(jìn)行參數(shù)調(diào)整。

節(jié)點(diǎn)評(píng)估算法的性能在很大程度上受到WSN動(dòng)態(tài)性的影響，如由新舊節(jié)點(diǎn)的替換帶來的網(wǎng)絡(luò)拓?fù)渥兓?、由?jié)點(diǎn)移動(dòng)引起的相對(duì)位置信息變化以及由收發(fā)數(shù)據(jù)包帶來的剩余能量信息變化等。因此，一個(gè)性能較好的路由協(xié)議應(yīng)該具有一定的動(dòng)態(tài)性來適應(yīng)WSN 網(wǎng)絡(luò)信息的動(dòng)態(tài)變化。本文提出一種節(jié)點(diǎn)動(dòng)態(tài)評(píng)估算法DAF，節(jié)點(diǎn)以剩余能量、距離和角度為評(píng)估準(zhǔn)則對(duì)鄰居節(jié)點(diǎn)進(jìn)行動(dòng)態(tài)評(píng)分。具體地，當(dāng)某節(jié)點(diǎn)發(fā)現(xiàn)鄰居節(jié)點(diǎn)關(guān)于某準(zhǔn)則狀態(tài)值發(fā)生變化時(shí)，使用FIS 來動(dòng)態(tài)構(gòu)建AHP 中的成對(duì)比較矩陣，然后使用AHP 來計(jì)算每個(gè)鄰居節(jié)點(diǎn)的評(píng)分，根據(jù)該評(píng)分選擇候選轉(zhuǎn)發(fā)節(jié)點(diǎn)以及接收節(jié)點(diǎn)。DAF 使得發(fā)送節(jié)點(diǎn)可以根據(jù)鄰居節(jié)點(diǎn)的信息變化來動(dòng)態(tài)更新候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，通過及時(shí)加入評(píng)分較高的節(jié)點(diǎn)并移出評(píng)分較低的節(jié)點(diǎn)來提高網(wǎng)絡(luò)性能。

2 技術(shù)介紹

2.1 層次分析法

AHP［13］是根據(jù)網(wǎng)絡(luò)系統(tǒng)理論和多目標(biāo)綜合評(píng)價(jià)方法提出的一種層次權(quán)重決策分析方法。一般而言，AHP 將目標(biāo)、準(zhǔn)則和候選者按不同層次進(jìn)行聚集組合，形成一個(gè)多層次的分析結(jié)構(gòu)模型，如圖1所示。

圖1 AHP 結(jié)構(gòu)Fig.1 The structure of AHP

2.1.1 準(zhǔn)則權(quán)重計(jì)算

為了計(jì)算準(zhǔn)則相對(duì)于目標(biāo)的權(quán)重，AHP 需要預(yù)先構(gòu)建一個(gè)成對(duì)比較矩陣，該矩陣主對(duì)角元素全為1，其余元素關(guān)于主對(duì)角元素互為倒數(shù)。假設(shè)有m個(gè)準(zhǔn)則，則該成對(duì)比較矩陣是一個(gè)m維方陣，其形式如式（1）所示：

矩陣元素aij通常由決策者主觀判斷確定，表示第i個(gè)準(zhǔn)則相對(duì)于第j個(gè)準(zhǔn)則的重要性。若決策者認(rèn)為第i個(gè)準(zhǔn)則比第j個(gè)準(zhǔn)則重要，則aij的取值范圍和含義如表1 所示。在決策者構(gòu)建好成對(duì)比較矩陣之后，計(jì)算矩陣最大特征值對(duì)應(yīng)的特征向量，歸一化后得到一個(gè)m維列向量，每一維數(shù)值表示對(duì)應(yīng)準(zhǔn)則相對(duì)于目標(biāo)的權(quán)重。

表1 矩陣元素取值及其含義Table 1 Values of matrix elements and their meanings

2.1.2 候選者權(quán)重與評(píng)分計(jì)算

假設(shè)有n個(gè)候選者，則該部分共有m個(gè)成對(duì)比較矩陣，每個(gè)矩陣都是n維方陣。按照上述求解方法，決策者需要預(yù)先構(gòu)建這m個(gè)成對(duì)比較矩陣，然后分別求解m個(gè)矩陣的最大特征值對(duì)應(yīng)的特征向量，將所有特征向量按列合并后組成一個(gè)新的n×m維矩陣，該矩陣表示所有候選者相對(duì)于所有準(zhǔn)則的權(quán)重，其中，第k列表示所有候選者相對(duì)于第k個(gè)準(zhǔn)則的權(quán)重。

將上述計(jì)算所得n×m維矩陣點(diǎn)乘2.1.1 節(jié)所得m維列向量，得到一個(gè)n維列向量，該向量每一維度數(shù)值表示對(duì)應(yīng)候選者相對(duì)于目標(biāo)的總評(píng)分。

2.2 模糊推理系統(tǒng)

FIS［14］通過將一系列清晰的輸入值模糊化，基于自定義模糊規(guī)則得到模糊輸出，再將模糊輸出去模糊化得到一個(gè)清晰的輸出值，如圖2 所示。FIS 中有2 個(gè)重要的概念，即隸屬函數(shù)和模糊規(guī)則。

圖2 FIS 結(jié)構(gòu)Fig.2 The structure of FIS

2.2.1 隸屬函數(shù)

一個(gè)模糊集合可以用一個(gè)語言變量來表述，對(duì)于某個(gè)特定的數(shù)值，其屬于某模糊集合的隸屬度就用隸屬函數(shù)來表示。一般地，隸屬函數(shù)的值域范圍為0～1，定義域包括輸入變量的所有取值。模糊集合、隸屬函數(shù)和輸入變量之間的關(guān)系如式（2）所示：

其中：A表示模糊集合；x是輸入變量；μA(x)表示x屬于A的隸屬度，即對(duì)應(yīng)的隸屬函數(shù)值；X是x的所有取值集合。

2.2.2 模糊規(guī)則

在一般情況下，一個(gè)具有2 個(gè)前提條件的模糊規(guī)則形式如式（3）所示：

其中：“如果”后面的內(nèi)容稱為前提；“那么”后面的內(nèi)容稱為結(jié)論。x和y均是輸入變量，z是輸出 量，“x屬于A”表示x屬于A的隸屬度，即μA(x)的值，同樣地，“y屬于B”即μB(y)的值。模糊規(guī)則的解釋一般有以下2 個(gè)步驟：

1）評(píng)估前提的隸屬度。

2）確定模糊輸出。

計(jì)算復(fù)合前提的隸屬度，首先要計(jì)算每個(gè)前提的隸屬度，然后根據(jù)規(guī)則中的連接詞（“且”“或”“非”）使用不同的方法求解復(fù)合前提的隸屬度。在模糊邏輯中，結(jié)論的隸屬度與前提的隸屬度保持一致。一個(gè)模糊推理系統(tǒng)一般有多條模糊規(guī)則，所有模糊規(guī)則并行執(zhí)行，都會(huì)產(chǎn)生一個(gè)模糊輸出。將所有模糊輸出聚合后形成一個(gè)模糊輸出集，再通過使用去模糊化方法即可求得一個(gè)清晰的輸出值，該輸出值就是整個(gè)模糊推理系統(tǒng)的輸出。

3 DAF 算法

節(jié)點(diǎn)從鄰居節(jié)點(diǎn)中選擇合適的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)并在需要發(fā)送數(shù)據(jù)時(shí)選擇其中一個(gè)節(jié)點(diǎn)作為接收節(jié)點(diǎn)，這是一個(gè)多目標(biāo)決策問題（Multiple Criteria Decision Making，MCDM）［15］。AHP 在解決多目標(biāo)決策問題時(shí)具有簡(jiǎn)單高效的優(yōu)勢(shì)，因此，本文在WSN 中引入AHP 來解決與節(jié)點(diǎn)相關(guān)的決策問題。

應(yīng)用AHP 的關(guān)鍵在于成對(duì)比較矩陣的構(gòu)建，其構(gòu)建特性具有一定的局限性：首先，成對(duì)比較矩陣需要決策者根據(jù)自己的主觀判斷或喜愛偏好來構(gòu)建，這往往會(huì)因?yàn)闆Q策者個(gè)人問題導(dǎo)致無法做出合理的判斷；其次，成對(duì)比較矩陣的構(gòu)建需要人為干預(yù)，因此，在系統(tǒng)運(yùn)行中無法完成矩陣構(gòu)建。

FIS 能夠使系統(tǒng)或控制器如同一個(gè)經(jīng)驗(yàn)豐富的專家或?qū)I(yè)的操作員，因此，本文通過在WSN 中引入FIS，使傳感器節(jié)點(diǎn)能夠像人類一樣思考，使得AHP 中成對(duì)比較矩陣的構(gòu)建可以在無人為干涉的條件下由傳感器節(jié)點(diǎn)獨(dú)立完成。通過為FIS 自定義合適的模糊隸屬函數(shù)和模糊規(guī)則，使得矩陣的構(gòu)建不僅可以基于專家建議和意見，還可以在WSN 運(yùn)行過程中動(dòng)態(tài)完成。

DAF 算法首先使用AHP 確定準(zhǔn)則之間的權(quán)重，其次在評(píng)估不同準(zhǔn)則下的鄰居節(jié)點(diǎn)時(shí)，使用FIS 動(dòng)態(tài)構(gòu)建AHP 中的成對(duì)比較矩陣，具體表現(xiàn)為：將節(jié)點(diǎn)信息作為FIS 的輸入，用FIS 的輸出來替代矩陣中的元素值。本文所使用的符號(hào)及解釋如表2 所示。

表2 符號(hào)含義Table 2 Symbolic meaning

3.1 準(zhǔn)則權(quán)重確定

為了更好地評(píng)估鄰居節(jié)點(diǎn)，本文定義3 個(gè)影響網(wǎng)絡(luò)性能的準(zhǔn)則，其歸一化方法及含義如表3所示。

表3 準(zhǔn)則信息Table 3 Criterion information

結(jié)合實(shí)驗(yàn)數(shù)據(jù)和經(jīng)驗(yàn)分析，本文構(gòu)建準(zhǔn)則的成對(duì)比較矩陣如式（4）所示，行（列）標(biāo)依次表示剩余能量、距離和角度。求解矩陣最大特征值對(duì)應(yīng)的特征向量，歸一化之后得到準(zhǔn)則權(quán)重向量ω=(0.54，0.30，0.16)，元素依次表示剩余能量、距離和角度的權(quán)重。

3.2 鄰居節(jié)點(diǎn)動(dòng)態(tài)評(píng)估

本文通過構(gòu)建AHP 成對(duì)比較矩陣，計(jì)算成對(duì)比較矩陣最大特征值對(duì)應(yīng)的特征向量，以評(píng)估鄰居節(jié)點(diǎn)。為了能夠動(dòng)態(tài)評(píng)估鄰居節(jié)點(diǎn)，需要實(shí)現(xiàn)成對(duì)比較矩陣動(dòng)態(tài)構(gòu)建，本文使用FIS 的輸出來代替成對(duì)比較矩陣的元素值，從而實(shí)現(xiàn)矩陣動(dòng)態(tài)構(gòu)建。

3.2.1 FIS 輸入值

為了使用同一套FIS 來構(gòu)建不同準(zhǔn)則的成對(duì)比較矩陣，本文在獲取FIS 輸入值時(shí)需要對(duì)不同準(zhǔn)則的歸一化值進(jìn)行處理，目的是屏蔽FIS 輸入值對(duì)應(yīng)的物理意義。剩余能量越多的節(jié)點(diǎn)重要性越大，相反地，距離越遠(yuǎn)、角度越大的節(jié)點(diǎn)重要性越小。通過實(shí)驗(yàn)數(shù)據(jù)和理論分析，本文使用插值法進(jìn)行函數(shù)擬合，如式（5）、式（6）所示，其中，式（5）的自變量是剩余能量歸一化值，式（6）的自變量是距離或角度的歸一化值，函數(shù)圖像如圖3 所示。

圖3 FIS 不同準(zhǔn)則下的輸入值Fig.3 FIS input values under different criteria

3.2.2 輸入和輸出隸屬函數(shù)

Triangular 函數(shù)［16］是最簡(jiǎn)單且常用的模糊隸屬函數(shù)，其函數(shù)圖像主要由3 個(gè)點(diǎn)構(gòu)成，形成一個(gè)三角形，又稱為三角形函數(shù)。Triangular函數(shù)表達(dá)如式（7）所示，圖像如圖4 所示。

圖4 三角形模糊隸屬函數(shù)Fig.4 Triangular fuzzy membership function

考慮到Triangular 函數(shù)設(shè)計(jì)簡(jiǎn)單、計(jì)算高效等特點(diǎn)，本文使用該函數(shù)來定義輸入和輸出隸屬函數(shù)。其中：輸入隸屬函數(shù)表示“合適度”，共有“低”“中”“高”3 個(gè)級(jí)別；輸出隸屬函數(shù)表示“重要性”，包括“同等”“重要”“非常重要”3 個(gè)級(jí)別。輸入和輸出隸屬函數(shù)的參數(shù)設(shè)置如表4 所示。

表4 輸入輸出隸屬函數(shù)參數(shù)設(shè)置Table 4 Input and output membership function parameters setting

3.2.3 模糊規(guī)則

本文使用Mamdani 模糊推理系統(tǒng)［17］，模糊規(guī)則如表5 所示，每個(gè)規(guī)則前提由2 個(gè)部分組成，通過“且”進(jìn)行連接。去模糊化方法使用重心法CoG（Center-of-Gravity）［18］，該方法計(jì)算簡(jiǎn)單且易于理解，已成為一種常用的去模糊化方法。重心法通過求解一個(gè)x值，使得過該值的垂線可將模糊集合平分為2 個(gè)面積相等的部分，如式（8）所示：

表5 模糊規(guī)則Table 5 Fuzzy rules

其中：μc(x)表示模糊集合。

構(gòu)造不同準(zhǔn)則對(duì)應(yīng)的成對(duì)比較矩陣均使用表5所示的模糊規(guī)則，且每次將2 個(gè)節(jié)點(diǎn)中數(shù)值較大的節(jié)點(diǎn)作為A，較小的節(jié)點(diǎn)作為B。通過該模糊系統(tǒng)得到的輸出值表示A 相對(duì)于B 的重要性，B 相對(duì)于A 的重要性利用成對(duì)比較矩陣的互反性求得。例如在構(gòu)建剩余能量矩陣時(shí)，規(guī)則2 被翻譯為：如果節(jié)點(diǎn)A 的剩余能量“合適度”是“高”且節(jié)點(diǎn)B 的剩余能量“合適度”是“中”，那么針對(duì)剩余能量準(zhǔn)則而言，節(jié)點(diǎn)A相對(duì)于節(jié)點(diǎn)B 是“重要”的。

3.3 算法描述

以構(gòu)建關(guān)于剩余能量準(zhǔn)則的成對(duì)比較矩陣為例，用FIS 輸出值代替矩陣某元素值的求解過程如算法1 所述，基于算法1，節(jié)點(diǎn)使用DAF 動(dòng)態(tài)評(píng)估鄰居節(jié)點(diǎn)的過程如算法2 所述。

算法1求解剩余能量成對(duì)比較矩陣元素對(duì)

算法2節(jié)點(diǎn)使用DAF 動(dòng)態(tài)評(píng)估鄰居節(jié)點(diǎn)

4 實(shí)驗(yàn)結(jié)果與分析

4.1 仿真設(shè)置和參數(shù)默認(rèn)值

本文使用文獻(xiàn)［19］中所提供的仿真平臺(tái)，在實(shí)驗(yàn)過程中，節(jié)點(diǎn)按照?qǐng)A形拓?fù)潆S機(jī)部署，sink 節(jié)點(diǎn)位于網(wǎng)絡(luò)中心，且擁有無限的能量，數(shù)據(jù)包由節(jié)點(diǎn)循環(huán)生成。每個(gè)節(jié)點(diǎn)的初始能量相同且有限，通信范圍相同且不變，節(jié)點(diǎn)各自選擇一個(gè)隨機(jī)的時(shí)間點(diǎn)周期性地在醒睡2 種模式下切換，默認(rèn)醒1 s，睡2 s。節(jié)點(diǎn)的坐標(biāo)通過基于RSSI（Received Signal Strength Indicator）測(cè)距模型［20］獲得。通信模型采用FSPM（Free Space Propagation Model）［21］，該模型假設(shè)節(jié)點(diǎn)的通信范圍是一個(gè)以節(jié)點(diǎn)為圓心、以通信范圍為半徑的圓，處于圓內(nèi)的節(jié)點(diǎn)都可正確接收信息。能量模型采用FORM（First Order Radio Model）［22］，傳輸一個(gè)kbit 長(zhǎng)度的數(shù)據(jù)包所需的能耗如式（9）所示，接收一個(gè)kbit 長(zhǎng)度的數(shù)據(jù)包所需的能耗如式（10）所示。其余默認(rèn)參數(shù)配置如表6 所示。

表6 實(shí)驗(yàn)?zāi)J(rèn)參數(shù)配置Table 6 Experiment default parameters configuration

4.2 對(duì)比實(shí)驗(yàn)及評(píng)估標(biāo)準(zhǔn)

4.2.1 對(duì)比算法

本文使用ORW［6］和ORR［7］作為對(duì)比算法：

1）ORW 算法中使用的路由參數(shù)是EDC，每個(gè)節(jié)點(diǎn)都有屬于自己的EDC 且僅當(dāng)網(wǎng)絡(luò)拓?fù)浒l(fā)生變化時(shí)節(jié)點(diǎn)的EDC 值才會(huì)被重新計(jì)算。發(fā)送節(jié)點(diǎn)每次從醒來的鄰居節(jié)點(diǎn)中選擇一個(gè)EDC 值最低的節(jié)點(diǎn)作為轉(zhuǎn)發(fā)節(jié)點(diǎn)，因此，EDC 值較低的節(jié)點(diǎn)會(huì)因?yàn)檗D(zhuǎn)發(fā)過多的數(shù)據(jù)包而導(dǎo)致能耗較高。

2）ORR 算法在EDC 的基礎(chǔ)上考慮節(jié)點(diǎn)的剩余能量，提出新的路由參數(shù)FS（Forwarder Score）。同時(shí)為了限制候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集的大小，sink 節(jié)點(diǎn)會(huì)周期性地收集所有鄰居節(jié)點(diǎn)的信息，然后計(jì)算出一個(gè)最大值n作為所有節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集最大值，該過程通常會(huì)消耗較多的能量。

4.2.2 評(píng)估標(biāo)準(zhǔn)

本文使用以下性能指標(biāo)作為算法的評(píng)估標(biāo)準(zhǔn)：

1）生命周期，表示第一個(gè)節(jié)點(diǎn)耗盡其初始能量時(shí)網(wǎng)絡(luò)生成的數(shù)據(jù)包總數(shù)。

2）能量消耗，表示當(dāng)sink 節(jié)點(diǎn)收集一定數(shù)量的數(shù)據(jù)包時(shí)網(wǎng)絡(luò)消耗的總能量。

3）平均冗余傳輸，表示每發(fā)送一個(gè)數(shù)據(jù)包所產(chǎn)生的平均冗余數(shù)據(jù)包。

4.3 結(jié)果分析

本文通過改變不同的參數(shù)值分別進(jìn)行實(shí)驗(yàn)。在生命周期實(shí)驗(yàn)中，將數(shù)據(jù)包大小設(shè)置為1 024 Byte，在能量消耗及平均冗余傳輸實(shí)驗(yàn)中，sink 節(jié)點(diǎn)接收數(shù)據(jù)包數(shù)量被固定為3 000。

4.3.1 節(jié)點(diǎn)數(shù)量對(duì)算法性能的影響

將節(jié)點(diǎn)數(shù)量從100 依次增加到200，其他默認(rèn)參數(shù)設(shè)置不變，實(shí)驗(yàn)結(jié)果如圖5～圖7 所示。

圖5 生命周期隨節(jié)點(diǎn)數(shù)量的變化情況Fig.5 Life cycle changes with the number of nodes

由圖5 可知，網(wǎng)絡(luò)生命周期隨節(jié)點(diǎn)數(shù)量增加而增加。節(jié)點(diǎn)數(shù)量增加導(dǎo)致網(wǎng)絡(luò)密度增加，節(jié)點(diǎn)間的平均距離縮短，節(jié)點(diǎn)間單跳傳輸能耗降低，因此，網(wǎng)絡(luò)生命周期延長(zhǎng)。DAF 基于預(yù)確定的評(píng)估準(zhǔn)則，節(jié)點(diǎn)優(yōu)先發(fā)送數(shù)據(jù)給那些剩余能量高、距離近、角度小的節(jié)點(diǎn)，因此其性能表現(xiàn)最好。由圖6 可知，網(wǎng)絡(luò)的能量消耗隨著節(jié)點(diǎn)數(shù)量增加而增加。網(wǎng)絡(luò)密度增加，導(dǎo)致數(shù)據(jù)包跳數(shù)增加，因此，每個(gè)數(shù)據(jù)包消耗的平均總能耗增加，即網(wǎng)絡(luò)的總能耗增加。DAF 保證了路由路徑盡可能地向sink 靠近，降低了路由的偏離程度，因此其性能更佳。由圖7 可知，平均冗余傳輸隨著節(jié)點(diǎn)數(shù)量增加而增加。網(wǎng)絡(luò)密度增加，鄰居節(jié)點(diǎn)數(shù)量增加，節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集也隨之增加，發(fā)送節(jié)點(diǎn)在選擇轉(zhuǎn)發(fā)節(jié)點(diǎn)的過程中產(chǎn)生了更多的冗余數(shù)據(jù)包。DAF 通過動(dòng)態(tài)地為節(jié)點(diǎn)進(jìn)行評(píng)分，從而有效減少了平均冗余傳輸。

圖6 能量消耗隨節(jié)點(diǎn)數(shù)量的變化情況Fig.6 Energy consumption changes with the number of nodes

圖7 平均冗余傳輸隨節(jié)點(diǎn)數(shù)量的變化情況Fig.7 Average redundant transmission changes with the number of nodes

4.3.2 醒睡周期對(duì)算法性能的影響

在本次實(shí)驗(yàn)中，節(jié)點(diǎn)醒周期被固定為1 s，睡周期從1 s 依次增加到5 s，其他默認(rèn)參數(shù)設(shè)置不變，實(shí)驗(yàn)結(jié)果如圖8～圖10 所示。

圖8 生命周期隨節(jié)點(diǎn)睡眠時(shí)長(zhǎng)的變化情況Fig.8 Life cycle changes with node sleep duration

由圖8可知，生命周期隨睡眠時(shí)長(zhǎng)的增加而減少。發(fā)送節(jié)點(diǎn)在發(fā)送數(shù)據(jù)包之前會(huì)不停地發(fā)送前導(dǎo)碼包，隨著節(jié)點(diǎn)的睡眠周期延長(zhǎng)，發(fā)送節(jié)點(diǎn)用于發(fā)送前導(dǎo)碼包的能耗越來越多，導(dǎo)致網(wǎng)絡(luò)的生命周期減少。DAF通過動(dòng)態(tài)更新候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集使得其性能較ORW 和ORR 更佳。由圖9可知，能量消耗隨睡眠時(shí)長(zhǎng)增加而增加。雖然能耗會(huì)因?yàn)槿哂喟鼫p少而減少，但是能耗更多地浪費(fèi)在發(fā)送前導(dǎo)碼包上。DAF性能較優(yōu)的理由如上所述。由圖10 可知，平均冗余傳輸隨睡眠時(shí)長(zhǎng)增加而減少。多個(gè)節(jié)點(diǎn)同時(shí)醒來的概率隨著睡眠時(shí)長(zhǎng)的增加而減少，因此，減少了冗余數(shù)據(jù)包的產(chǎn)生。從實(shí)驗(yàn)結(jié)果來看，DAF 在平均冗余傳輸指標(biāo)上較ORW 和ORR 略優(yōu)。

圖9 能量消耗隨節(jié)點(diǎn)睡眠時(shí)長(zhǎng)的變化情況Fig.9 Energy consumption changes with node sleep duration

圖10 平均冗余傳輸隨節(jié)點(diǎn)睡眠時(shí)長(zhǎng)的變化情況Fig.10 Average redundant transmission changes with node sleep duration

4.3.3 通信半徑對(duì)算法性能的影響

將節(jié)點(diǎn)通信半徑從50 m 依次增加到90 m，其他默認(rèn)參數(shù)設(shè)置不變，實(shí)驗(yàn)結(jié)果如圖11～圖13 所示。

圖11 生命周期隨通信半徑的變化情況Fig.11 Life cycle changes with communication radius

由圖11 可知，網(wǎng)絡(luò)生命周期隨通信半徑增加而減少。通信半徑增加，導(dǎo)致候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集中包含更遠(yuǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，當(dāng)數(shù)據(jù)包通過這些較遠(yuǎn)的節(jié)點(diǎn)進(jìn)行轉(zhuǎn)發(fā)時(shí)，單跳數(shù)據(jù)包能耗增加，因此，生命周期呈下降趨勢(shì)。DAF 通過距離準(zhǔn)則評(píng)估鄰居節(jié)點(diǎn)，從而在一定程度上避免了距離較遠(yuǎn)的鄰居節(jié)點(diǎn)被選擇加入候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，因此，其單跳能耗更低，生命周期相對(duì)較長(zhǎng)。

由圖12 可知，能量消耗隨通信半徑增加而先降低后提高。隨著通信半徑的增加，數(shù)據(jù)包的跳數(shù)減少，能耗隨著跳數(shù)的減少而減少，因此，先呈現(xiàn)下降趨勢(shì)。但是，由于式（9）中的距離閾值，隨著通信范圍的繼續(xù)增加，用于發(fā)送數(shù)據(jù)包的能耗大幅增加，使得能耗呈現(xiàn)上升趨勢(shì)。DAF 考慮距離標(biāo)準(zhǔn)，在一定程度上控制了數(shù)據(jù)包的單跳能耗，因此，其性能表現(xiàn)更佳。

圖12 能量消耗隨通信半徑的變化情況Fig.12 Energy consumption changes with communication radius

由圖13 可知，平均冗余傳輸隨通信半徑的增加而增加。通信半徑的增加直接導(dǎo)致節(jié)點(diǎn)的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集增加，因此，在發(fā)送數(shù)據(jù)包的過程中產(chǎn)生了更多的冗余數(shù)據(jù)包。DAF 動(dòng)態(tài)選擇候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集，使得其性能優(yōu)于ORW 和ORR。

圖13 平均冗余傳輸隨通信半徑的變化情況Fig.13 Average redundant transmission changes with communication radius

5 結(jié)束語

在基于異步醒睡機(jī)制的WSN 中，傳感器節(jié)點(diǎn)通常會(huì)選擇多個(gè)節(jié)點(diǎn)作為候選轉(zhuǎn)發(fā)節(jié)點(diǎn)，任何一個(gè)醒來的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)均可進(jìn)行數(shù)據(jù)路由。因此，候選節(jié)點(diǎn)的選擇對(duì)網(wǎng)絡(luò)性能有較大影響，動(dòng)態(tài)路由算法可以很好地適應(yīng)WSN 中網(wǎng)絡(luò)節(jié)點(diǎn)信息或拓?fù)浣Y(jié)構(gòu)實(shí)時(shí)變化的特性。本文提出一種動(dòng)態(tài)評(píng)估鄰居節(jié)點(diǎn)的路由算法DAF，在網(wǎng)絡(luò)運(yùn)行中根據(jù)節(jié)點(diǎn)信息并使用FIS 動(dòng)態(tài)構(gòu)建AHP 中的成對(duì)比較矩陣，從而選擇出更合理的候選轉(zhuǎn)發(fā)節(jié)點(diǎn)集。實(shí)驗(yàn)結(jié)果表明，與ORW 和ORR 算法相比，該算法能夠有效提高網(wǎng)絡(luò)生命周期，減少能量消耗和冗余數(shù)據(jù)包。下一步考慮在硬件上真實(shí)部署傳感器網(wǎng)絡(luò)，并在能量以及計(jì)算能力均不受限的WSN 中進(jìn)行路由算法設(shè)計(jì)。