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

周文康，王行甫

（1.中國科學技術大學 網絡空間安全學院，合肥 230022；2.中國科學技術大學 計算機科學與技術學院，合肥 230022）

0 概述

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

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

WSN 中通常有2 種介質訪問控制（Medium Access Control，MAC）協議，即同步MAC 協議和異步MAC 協議。在同步MAC 協議中，所有節點都在同一時刻醒來，發送節點可以直接將數據發送給接收節點而不需要等待；在異步MAC 協議中，發送節點往往會花費很長時間等待接收節點醒來然后才能發送數據，這將大幅增加發送節點的等待時延。

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

由以上分析可知，候選轉發節點的評估與選擇對網絡性能影響較大。為了更好地對節點進行評估，選擇更合理的候選轉發節點集，本文基于層次分析法（Analytic Hierarchy Process，AHP）和模糊推理系統（Fuzzy Inference System，FIS），提出一種DAF（Dynamic evaluation algorithm based on AHP and FIS）算法，該算法在網絡運行的過程中根據節點信息使用FIS 動態構建AHP 中的成對比較矩陣，從而實現對鄰居節點的動態評分。

1 相關工作

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

文獻［3］提出一個異步MAC 協議B-MAC，當發送節點有數據包要發送時，會先發送一個前導碼包給鄰居節點，詢問它們的狀態信息，處于醒模式下的鄰居節點會接收該前導碼包并發回一個ACK 確認包，發送節點在接收到這些ACK 之后會從中選擇一個節點作為接收節點并將數據包轉發給該節點，如果沒有鄰居節點醒來，即發送節點接收不到ACK，則會不間斷地發送前導碼包。文獻［4］提出另一種異步MAC 協議X-MAC，相較于B-MAC，X-MAC 發送的前導碼包較短。文獻［5］提出BoX-MAC，該協議通過共享物理層和數據鏈路層的信息來減少節點的能量消耗從而提高網絡性能。

文獻［6］基于ETX（Expected Transmission Count）提出一種路由參數EDC（Expected Duty Cycled wake-ups），其表示到達sink 節點所需要的平均醒睡周期數，EDC越小的節點表示離sink 越近，且只有當網絡拓撲發生變化時EDC 才會改變。發送節點會選擇EDC 較小的節點作為轉發節點，因此，這些節點往往會因為接收過多的數據包而導致能量消耗比其他節點更快。

文獻［7］在EDC 的基礎上考慮節點的剩余能量，剩余能量越高的節點越有可能被選擇作為接收節點，EDC 較小的節點會因為其剩余能量較低而被選擇作為接收節點的優先級降低，因此，其能均衡網絡負載并提高網絡生命周期。

在文獻［8］中，數據包被節點接收后不會被立即轉發，若在短時間內有新的數據包被接收，則該節點會將這些數據包進行融合之后再發送，通過減少發送次數來節省能耗，但是這對數據融合算法提出了較高的要求，當網絡數據傳輸率較低時，往往在網絡性能上表現不佳。

文獻［9］提出一種自適應路由協議AOR（Adaptive Opportunistic Routing），其采用分區方案來提高網絡的吞吐量，即根據節點和匯聚節點之間的位置關系，將整個網絡分成不同的區域，每個區域擁有不同的優先級。但是，由于區域劃分的計算量較大且無法實現動態計算，因此在網絡拓撲發生動態變化時，無法準確地將不同位置的節點劃入不同的區域中，從而導致網絡性能下降。

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

文獻［11］提出方向分布、傳輸距離分布、垂直距離分布、剩余能量分布這4 種分布，通過參數控制4 種分布的權重，最終計算出每個節點的得分。同時，為每個節點定義一個矩形范圍，稱為CZ（Candidates Zone），只有CZ 中的節點才可被選擇作為轉發節點。但是，該網絡性能在很大程度上受到參數的影響，在網絡運行過程中，參數不可動態改變，因此，很難在網絡運行之前確定合理的分布權重參數。

文獻［12］為了提高WSN 路由算法的靈活性，提出一種新的路由算法FRCA，在該算法中，節點的轉發概率取決于多個部分，包括影響網絡性能的物理量、基本的數學函數以及路由參數，通過調整各個部分的參數權重，最終計算出節點的路由度量，在節點轉發數據包時用該度量來進行接收節點的選擇。但是，針對不同的網絡應用來調整一組合適的路由參數非常困難，且當網絡拓撲發生變化時該算法不能在運行過程中進行參數調整。

節點評估算法的性能在很大程度上受到WSN動態性的影響，如由新舊節點的替換帶來的網絡拓撲變化、由節點移動引起的相對位置信息變化以及由收發數據包帶來的剩余能量信息變化等。因此，一個性能較好的路由協議應該具有一定的動態性來適應WSN 網絡信息的動態變化。本文提出一種節點動態評估算法DAF，節點以剩余能量、距離和角度為評估準則對鄰居節點進行動態評分。具體地，當某節點發現鄰居節點關于某準則狀態值發生變化時，使用FIS 來動態構建AHP 中的成對比較矩陣，然后使用AHP 來計算每個鄰居節點的評分，根據該評分選擇候選轉發節點以及接收節點。DAF 使得發送節點可以根據鄰居節點的信息變化來動態更新候選轉發節點集，通過及時加入評分較高的節點并移出評分較低的節點來提高網絡性能。

2 技術介紹

2.1 層次分析法

AHP［13］是根據網絡系統理論和多目標綜合評價方法提出的一種層次權重決策分析方法。一般而言，AHP 將目標、準則和候選者按不同層次進行聚集組合，形成一個多層次的分析結構模型，如圖1所示。

圖1 AHP 結構Fig.1 The structure of AHP

2.1.1 準則權重計算

為了計算準則相對于目標的權重，AHP 需要預先構建一個成對比較矩陣，該矩陣主對角元素全為1，其余元素關于主對角元素互為倒數。假設有m個準則，則該成對比較矩陣是一個m維方陣，其形式如式（1）所示：

矩陣元素aij通常由決策者主觀判斷確定，表示第i個準則相對于第j個準則的重要性。若決策者認為第i個準則比第j個準則重要，則aij的取值范圍和含義如表1 所示。在決策者構建好成對比較矩陣之后，計算矩陣最大特征值對應的特征向量，歸一化后得到一個m維列向量，每一維數值表示對應準則相對于目標的權重。

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

2.1.2 候選者權重與評分計算

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

將上述計算所得n×m維矩陣點乘2.1.1 節所得m維列向量，得到一個n維列向量，該向量每一維度數值表示對應候選者相對于目標的總評分。

2.2 模糊推理系統

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

圖2 FIS 結構Fig.2 The structure of FIS

2.2.1 隸屬函數

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

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

2.2.2 模糊規則

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

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

1）評估前提的隸屬度。

2）確定模糊輸出。

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

3 DAF 算法

節點從鄰居節點中選擇合適的候選轉發節點并在需要發送數據時選擇其中一個節點作為接收節點，這是一個多目標決策問題（Multiple Criteria Decision Making，MCDM）［15］。AHP 在解決多目標決策問題時具有簡單高效的優勢，因此，本文在WSN 中引入AHP 來解決與節點相關的決策問題。

應用AHP 的關鍵在于成對比較矩陣的構建，其構建特性具有一定的局限性：首先，成對比較矩陣需要決策者根據自己的主觀判斷或喜愛偏好來構建，這往往會因為決策者個人問題導致無法做出合理的判斷；其次，成對比較矩陣的構建需要人為干預，因此，在系統運行中無法完成矩陣構建。

FIS 能夠使系統或控制器如同一個經驗豐富的專家或專業的操作員，因此，本文通過在WSN 中引入FIS，使傳感器節點能夠像人類一樣思考，使得AHP 中成對比較矩陣的構建可以在無人為干涉的條件下由傳感器節點獨立完成。通過為FIS 自定義合適的模糊隸屬函數和模糊規則，使得矩陣的構建不僅可以基于專家建議和意見，還可以在WSN 運行過程中動態完成。

DAF 算法首先使用AHP 確定準則之間的權重，其次在評估不同準則下的鄰居節點時，使用FIS 動態構建AHP 中的成對比較矩陣，具體表現為：將節點信息作為FIS 的輸入，用FIS 的輸出來替代矩陣中的元素值。本文所使用的符號及解釋如表2 所示。

表2 符號含義Table 2 Symbolic meaning

3.1 準則權重確定

為了更好地評估鄰居節點，本文定義3 個影響網絡性能的準則，其歸一化方法及含義如表3所示。

表3 準則信息Table 3 Criterion information

結合實驗數據和經驗分析，本文構建準則的成對比較矩陣如式（4）所示，行（列）標依次表示剩余能量、距離和角度。求解矩陣最大特征值對應的特征向量，歸一化之后得到準則權重向量ω=(0.54，0.30，0.16)，元素依次表示剩余能量、距離和角度的權重。

3.2 鄰居節點動態評估

本文通過構建AHP 成對比較矩陣，計算成對比較矩陣最大特征值對應的特征向量，以評估鄰居節點。為了能夠動態評估鄰居節點，需要實現成對比較矩陣動態構建，本文使用FIS 的輸出來代替成對比較矩陣的元素值，從而實現矩陣動態構建。

3.2.1 FIS 輸入值

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

圖3 FIS 不同準則下的輸入值Fig.3 FIS input values under different criteria

3.2.2 輸入和輸出隸屬函數

Triangular 函數［16］是最簡單且常用的模糊隸屬函數，其函數圖像主要由3 個點構成，形成一個三角形，又稱為三角形函數。Triangular函數表達如式（7）所示，圖像如圖4 所示。

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

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

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

3.2.3 模糊規則

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

表5 模糊規則Table 5 Fuzzy rules

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

構造不同準則對應的成對比較矩陣均使用表5所示的模糊規則，且每次將2 個節點中數值較大的節點作為A，較小的節點作為B。通過該模糊系統得到的輸出值表示A 相對于B 的重要性，B 相對于A 的重要性利用成對比較矩陣的互反性求得。例如在構建剩余能量矩陣時，規則2 被翻譯為：如果節點A 的剩余能量“合適度”是“高”且節點B 的剩余能量“合適度”是“中”，那么針對剩余能量準則而言，節點A相對于節點B 是“重要”的。

3.3 算法描述

以構建關于剩余能量準則的成對比較矩陣為例，用FIS 輸出值代替矩陣某元素值的求解過程如算法1 所述，基于算法1，節點使用DAF 動態評估鄰居節點的過程如算法2 所述。

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

算法2節點使用DAF 動態評估鄰居節點

4 實驗結果與分析

4.1 仿真設置和參數默認值

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

表6 實驗默認參數配置Table 6 Experiment default parameters configuration

4.2 對比實驗及評估標準

4.2.1 對比算法

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

1）ORW 算法中使用的路由參數是EDC，每個節點都有屬于自己的EDC 且僅當網絡拓撲發生變化時節點的EDC 值才會被重新計算。發送節點每次從醒來的鄰居節點中選擇一個EDC 值最低的節點作為轉發節點，因此，EDC 值較低的節點會因為轉發過多的數據包而導致能耗較高。

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

4.2.2 評估標準

本文使用以下性能指標作為算法的評估標準：

1）生命周期，表示第一個節點耗盡其初始能量時網絡生成的數據包總數。

2）能量消耗，表示當sink 節點收集一定數量的數據包時網絡消耗的總能量。

3）平均冗余傳輸，表示每發送一個數據包所產生的平均冗余數據包。

4.3 結果分析

本文通過改變不同的參數值分別進行實驗。在生命周期實驗中，將數據包大小設置為1 024 Byte，在能量消耗及平均冗余傳輸實驗中，sink 節點接收數據包數量被固定為3 000。

4.3.1 節點數量對算法性能的影響

將節點數量從100 依次增加到200，其他默認參數設置不變，實驗結果如圖5～圖7 所示。

圖5 生命周期隨節點數量的變化情況Fig.5 Life cycle changes with the number of nodes

由圖5 可知，網絡生命周期隨節點數量增加而增加。節點數量增加導致網絡密度增加，節點間的平均距離縮短，節點間單跳傳輸能耗降低，因此，網絡生命周期延長。DAF 基于預確定的評估準則，節點優先發送數據給那些剩余能量高、距離近、角度小的節點，因此其性能表現最好。由圖6 可知，網絡的能量消耗隨著節點數量增加而增加。網絡密度增加，導致數據包跳數增加，因此，每個數據包消耗的平均總能耗增加，即網絡的總能耗增加。DAF 保證了路由路徑盡可能地向sink 靠近，降低了路由的偏離程度，因此其性能更佳。由圖7 可知，平均冗余傳輸隨著節點數量增加而增加。網絡密度增加，鄰居節點數量增加，節點的候選轉發節點集也隨之增加，發送節點在選擇轉發節點的過程中產生了更多的冗余數據包。DAF 通過動態地為節點進行評分，從而有效減少了平均冗余傳輸。

圖6 能量消耗隨節點數量的變化情況Fig.6 Energy consumption changes with the number of nodes

圖7 平均冗余傳輸隨節點數量的變化情況Fig.7 Average redundant transmission changes with the number of nodes

4.3.2 醒睡周期對算法性能的影響

在本次實驗中，節點醒周期被固定為1 s，睡周期從1 s 依次增加到5 s，其他默認參數設置不變，實驗結果如圖8～圖10 所示。

圖8 生命周期隨節點睡眠時長的變化情況Fig.8 Life cycle changes with node sleep duration

由圖8可知，生命周期隨睡眠時長的增加而減少。發送節點在發送數據包之前會不停地發送前導碼包，隨著節點的睡眠周期延長，發送節點用于發送前導碼包的能耗越來越多，導致網絡的生命周期減少。DAF通過動態更新候選轉發節點集使得其性能較ORW 和ORR 更佳。由圖9可知，能量消耗隨睡眠時長增加而增加。雖然能耗會因為冗余包減少而減少，但是能耗更多地浪費在發送前導碼包上。DAF性能較優的理由如上所述。由圖10 可知，平均冗余傳輸隨睡眠時長增加而減少。多個節點同時醒來的概率隨著睡眠時長的增加而減少，因此，減少了冗余數據包的產生。從實驗結果來看，DAF 在平均冗余傳輸指標上較ORW 和ORR 略優。

圖9 能量消耗隨節點睡眠時長的變化情況Fig.9 Energy consumption changes with node sleep duration

圖10 平均冗余傳輸隨節點睡眠時長的變化情況Fig.10 Average redundant transmission changes with node sleep duration

4.3.3 通信半徑對算法性能的影響

將節點通信半徑從50 m 依次增加到90 m，其他默認參數設置不變，實驗結果如圖11～圖13 所示。

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

由圖11 可知，網絡生命周期隨通信半徑增加而減少。通信半徑增加，導致候選轉發節點集中包含更遠的候選轉發節點，當數據包通過這些較遠的節點進行轉發時，單跳數據包能耗增加，因此，生命周期呈下降趨勢。DAF 通過距離準則評估鄰居節點，從而在一定程度上避免了距離較遠的鄰居節點被選擇加入候選轉發節點集，因此，其單跳能耗更低，生命周期相對較長。

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

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

由圖13 可知，平均冗余傳輸隨通信半徑的增加而增加。通信半徑的增加直接導致節點的候選轉發節點集增加，因此，在發送數據包的過程中產生了更多的冗余數據包。DAF 動態選擇候選轉發節點集，使得其性能優于ORW 和ORR。

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

5 結束語

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