基于Grover融合理論的無線傳感網絡路由算法研究*

丁偉杰，周凱，周國民，王勛

（1.浙江警察學院計算機與信息技術系，杭州310053；2.浙江工業大學信息工程學院，杭州310023；3.浙江工業大學理學院，杭州310023）

基于Grover融合理論的無線傳感網絡路由算法研究*

丁偉杰1，2，周凱3*，周國民1，王勛1

（1.浙江警察學院計算機與信息技術系，杭州310053；2.浙江工業大學信息工程學院，杭州310023；3.浙江工業大學理學院，杭州310023）

如何在各種網絡資源受限制的情況，實現高質量的信息傳輸是無線傳感網絡研究領域的關鍵問題之一。首先，分析了網絡傳輸中所需要考慮的受限制因素，并提出各種因素的計算辦法；然后，針對確保服務質量的多目標規劃算法存在計算量過大的缺陷，借鑒量子搜索算法中的Grover理論用以降低信息傳輸過程的搜索計算量；最后，通過Grover理論得到的各種資源路由選擇方案，本文采用了計算機控制中的D-S信息融合理論，將多目標規劃轉化為單目標規劃。為了驗證本文所提出的Grover融合路由算法，文章建立MATLAB仿真環境，對比傳統的DSR路由協議與多目標規劃TOPSIS算法，可見本文所提出的算法在降低網絡搜索計算量、延長網絡生存時間、降低網絡時延方面具有較大的改善。

路由協議；多目標規劃；Grover算法；數據融合；TOPSIS

EEACC：7230doi：10.3969/j.issn.1004-1699.2016.09.022

無線傳感器網絡WSN（Wireless Sensor Net?work）是一種由大量可自組織形成多跳無線網絡的傳感節點構成，并實現信息處理與傳輸的新型網絡。由于無線傳感網絡組網靈活，不受現有基礎設備約束等優勢，因而被廣泛地應用于軍事、醫療等領域中［1］，引起了國內外學者的廣泛關注。其中，網絡路由協議就是無線傳感網絡研究的熱點領域之一。由于傳統的分布式路由協議以網絡節點為中心，造成網絡節點計算量都較大，且無線傳感網絡的布網環境較有線網絡更為惡劣，許多網絡資源受到制約（如網絡中節點的能量有限）［2］，因此傳統的路由協議并不適用于無線傳感網絡。探索一種能夠在資源受限的情況，確保高質量信息傳輸的路由協議顯得尤為重要。

國內學者對于無線傳感網絡路由協議的研究起源于2001年，有大量關于多跳路由協議的論文相繼被發表。相比有限網絡路由協議，無線傳感網絡信息傳輸過程中，需要兼顧更多的影響因素（如網絡節點能量消耗、網絡傳輸時延、分組丟失率等等）。因此，如何在網絡資源受限時，提供高質量的信息服務顯得更為重要。有相關文獻指出［3］：當路由選擇時的約束條件包含兩個或者兩個以上參數組合時，該路由問題便是一個NP完全問題，即多項式復雜程度的非確定性問題，該問題無法使用傳統的算法就行求解。國內外的專家也針對這個問題展開了一些研究。如文獻［4］提出利用串聯排隊的方法，降低網絡路由的搜索量，實現網絡中信息傳輸的服務質量保障。文獻［5］對最重要的幾個因素Top-k服務組合進行建模，采用啟發式算法（貪婪算法）縮小求解空間，從而實現網絡中信息傳輸的服務質量保障。

由于無線傳感網絡中的節點計算能力弱，無法實現高質量的實時語音和圖像的傳輸［6］。為了能夠在網絡中傳輸高質量的傳輸服務，同時又能降低網絡節點的計算量，本文提出了一種Grover融合的新型無線傳感網絡路由算法。本文分析了網絡傳輸中所需要考慮的受限制因素，并提出各種因素的計算辦法；然后，針對確保服務質量的多目標規劃算法存在計算量過大的缺陷，借鑒量子搜索算法中的Grover理論用以降低信息傳輸過程的搜索計算量；最后，通過Grover理論得到的各種資源路由選擇方案，本文采用了計算機控制中的D-S信息融合理論，將多目標規劃問題轉化為單目標規劃問題。

1　網絡關鍵參數計算方法

在一個由N個節點組成的M×M正方形無線傳感網絡中，Xi（t）表示在時刻t節點i的位置。無線傳感網絡中，每一個節點都有一個受限的通信半徑R。如果兩個節點間的距離小于R，則說明節點間可以直接通信；否則節點間需要通過中間節點轉發才可以進行通信。在時刻t，節點i和節點j之間的距離lij（t）可以表達如下：

當僅考慮網絡時延進行信息傳輸時，優先考慮時延較少的鏈路，因此每一條路的被選擇概率與該條鏈路的時延成反比，與該條鏈路的長度成反比。

無線傳感網絡中的節點間是靠無線電進行通信。為此，本文可以建立一階能量消耗模型［9］，如圖1所示。

圖1　一階能量消耗模型

發送數據包消耗能量包括發射電路耗能、放大電路耗能兩部分，接收數據只有接收電路消耗能量。一階能量消耗模型數學模型可以表示如式所示［10］：

其中，ETx表示發送者能量消耗，ERx表示接收者能量消耗，Eelec表示發射電路和接收電路的能耗，L表示發送數據包包含的比特數，l表示傳輸距離，εfs是常數。上述參數典型值為：Eelec=50 nJ/bit，εfs=10 pJ/（bit/m2）。

每條鏈路的剩余能量由組成該條鏈路的兩端節點剩余能量決定。當兩端節點中的任一節點剩余能量耗盡時，該條鏈路也便宣告失效。因此，鏈路→的剩余能量Egij（t）表達如下：

其中，Ei（t）表示節點i在當前時刻的剩余能量；Ej（t）表示節點j在當前時刻的剩余能量。

當僅考慮節點剩余能量進行路由選擇時，優先選擇剩余能量較高的鏈路進行信息轉發。因此每一條路的被選擇概率與該條鏈路的剩余能量成正比。

2　Grover融合多目標路由數學模型

Grover搜索思想的特點在于利用矩陣運算的優勢，對各種存在的各種可能解徑概率進行變換，從而達到放大正確解徑概率，降低非正確解徑概率的目的。通過分析可知：運用Grover算法進行搜索的關鍵就在于構造合適的操作矩陣和概率擴散矩陣［11］。與文獻［11］中所構造的操作矩陣、擴散矩陣的方法所有不同：文獻中構造的兩種矩陣皆以網絡分布式節點為主體進行鏈路的被選擇概率計算，從而提高正確的節點被選擇概率。而本文研究所針對的時延、剩余能量皆以網絡中的鏈路為主體，從而提高能夠確保高質量信息傳輸服務的鏈路被選擇概率。因此，本文所構造的兩個矩陣也是以鏈路為主體而進行展開。

對于一個N節點構成的無線傳感網絡將會形成N2條可能的鏈路。整個網絡維護著兩個N2×N2鏈路操作矩陣

擴散矩陣的作用在于放大正確的解徑，使得路由搜索快速收斂，該矩陣在整個路由搜索過程中保持恒定不變［12］?？梢宰C明該矩陣滿足幺正矩陣的條件，構建N2×N2的概率擴散矩陣D=（dmn）N2×N2的方式如下所示：

在路由搜索過程中，定義1×N2鏈路振幅矩陣W=（?m）1×N2，用于記錄各條鏈路的振幅，表示鏈路被選擇的概率。每條鏈路的初始振幅都相等表示如下：

根據被測概率等于振幅的平方，滿足振幅的平方和等于1的條件。因為操作矩陣不是單位矩陣，所以得到的概率矢量需要進行歸一化處理。歸一化以后，鏈路基于能量選擇的概率和基于時延選擇的概率表達如下：

通過Grover計算后的每條鏈路都會得到兩個被選擇概率，分別對應著剩余能量與時延，形成兩個網絡概率矩陣和這是一個多目標規劃問題。本文引入人工智能領域中的D-S證據理論［13］，將鏈路能量信息和時延信息進行融合，得到每條鏈路選擇概率計算公式如下：

3　網絡仿真

為了進一步分析本文所提出Grover融合路由算法的性能，建立了網絡仿真模型對協議進行分析。在一個300 m×300 m的矩形無線傳感網絡中，隨機分布50個無線節點，兩兩之間產生1 225個業務通信請求，采用MATLAB軟件進行仿真分析。

為了與本文提出的Grover融合路由算法進行性能比較，本文引入動態源路由協議DSR（Dynamic Source Routing Protocol）與理想狀態多目標算法TOPSIS（Technique for Order Preference by Similarity to an Ideal Solution）。其中，DSR是一種專門為多跳無線傳感網絡而設計的簡單、高效的路由協議，該協議動態地維護著網絡中所有的路由信息，并進行適時、自動更新。當需要建立路由時，該路由協議可以提供快速反應服務。在DSR路由協議的基礎上，考慮網絡時延、能量消耗兩個網絡關鍵指標，運用TOPSIS算法進行多目標規劃的路徑選擇。TOPSIS求解過程中先依次最優化各個分目標（網絡能耗和網絡時延），然后在某種意義下使向量目標函數與所考慮問題的理想點的偏差為極小。

在如上的無線傳感網絡環境中，進行1 225次的業務量仿真，對比兩種算法在計算量上的性能差異，部分效果如圖2所示。

圖2　兩種路由策略計算量對比圖

從圖2可以發現：對于相同的業務請求，兩種協議在路由搜索過程中，Grover融合路由算法在網絡計算量上普遍低于由DSR-TOPSIS路由協議所產生的計算量?？梢?，Grover算法的確可以有效地降低由多目標規劃問題產生的高計算量問題。

為了評價路由算法在延長網絡生存時間所產生的作用，將網絡中第一個節點由于能量耗盡退出網絡的時間定義為網絡生存時間的指標。第一個節點退出網絡的時間越遲，說明網絡的生存時間越長。因此，也將網絡中能量最低的節點稱為瓶頸節點。定義網絡中每個節點最初時的能量為“1”，運用兩種路由協議分別對無線傳感網絡中的1 225個業務請求進行路由搜索，得到網絡中瓶頸節點的能量變化情況如圖3所示。從圖3可以發現：Grover融合路由算法可以使得網絡瓶頸節點能量降低較為緩慢，從而延長網絡生存時間?？梢?，相比于DSR-TOPSIS路由協議，Grover融合路由算法更加有利于延長網絡生存時間。

圖3　兩種算法下瓶頸節點的能量變化圖

本文主要考察網絡生存時間與網絡時延兩項網絡關鍵參數。運用兩種路由算法分別對無線傳感網絡中的1 225次業務請求進行路由搜索，并記錄每次業務信息傳輸產生的時延，結果如圖4所示。從圖4可以發現：Grover融合路由算法的時延普遍低于DSR-TOPSIS路由協議。

圖4　兩種算法下網絡業務傳輸時延變化圖

4　結束語

為了確保高質量的網絡信息傳輸，本文提出了一種基于Grover融合思想的無線傳感網絡路由算法。在該算法中，通過Grover量子搜索算法降低網絡多目標規劃的計算量，然后使用D-S融合理論將各指標下的鏈路概率進行融合得到每條鏈路的最終選擇概率，解決多目標決策的難題。對比于其他的無線傳感網絡路由協議，本文提出的算法能夠有效地降低計算量、延遲網絡生存時間、降低網絡傳輸的時延。

［1］Jae Young Seol，Seong Lyun Kim.Node Mobility and Capacity in Wireless Controllable Ad Hoc Networks［J］.Computer Communi?cations，2012，35（11）：1345-1354.

［2］Vishwanath Ramamurthi，Abu（Sayeem）Reaz，Dipak Ghosal，et al.Channel，Capacity，and Flow Assignment in Wireless Mesh Networks［J］.Computer Networks，2011，55（9）：2241-2258.

［3］Liu Min，Xu Shijun，Sun Siyi.An Agent-Assisted QoS-Based Routing Algorithm for Wireless Sensor Networks［J］.Journal of Network and Computer Applications，2012，35（1）：29-36.

［4］Song Guo，Oliver Yang.QoS-Aware Minimum Energy Multicast Tree Construction in Wireless Ad Hoc Networks［J］.Ad Hoc Net?works.2004，2（3）：217-229.

［5］楊汝濤，張紹謙，竇萬春.一種基于QoS剪枝的Top-k自動服務組合方法［J］.電子學報，2012，40（7）：1489-1491.

［6］郝曉辰，竇晶晶，劉彬.基于路徑損耗的無線傳感器網絡分布式拓撲控制算法［J］.軟件學報.2009，20（12）：3213-3222.

［7］姜向遠，張煥水，王偉.一種基于非完全數據的路徑損耗模型選擇算法［J］.電子與信息學報，2012，34（6）：1438-1344.

［8］Junhua Zhu，Ka-Lok Hung，Brahim Bensaou，et al.Rate-Lifetime Tradeoff for Reliable Communication in Wireless Sensor Networks［J］.Computer Networks，2008，52（1）：25-43.

［9］楊明，羅軍舟，劉波.多射頻無線Mesh網絡組播端到端時延建模與優化［J］.計算機學報，2012，35（7）：1358-1369.

［10］Abbas Nayebi，Hamid Sarbazi-Azad.Performance Modeling of the LEACH Protocol for Mobile Wireless Sensor Networks［J］.Jour?nal of Parallel and Distributed Computing.2011，71（6）：812-821.

［11］Geetha V，Kallapur P V，Sushma Tellajeera.Clustering in Wire?less Sensor Networks：Performance Comparison of LEACH& LEACH-C Protocols Using NS2［J］.Procedia Technology，2012，4：163-170.

［12］Luan Linlin，Wang Zhijie，Liu Sanming.Progress of Grover Quan?tum Search Algorithm［J］.Energy Procedia，2012，6：1701-1706.

［13］Ai Lingmei，Wang Jue，Wang Xuelian.Multi-Features Fusion Di?agnosis of Tremor Based on Artificial Neural Network and D-S Ev?idence Theory［J］.Signal Processing，2008，88（12）：2927-2935.

丁偉杰（1980-）男，河南西平人，浙江警察學院計算機與信息技術系講師，浙江工業大學信息工程學院博士研究生。主要研究方向為信號處理，計算機網絡建模，圖像處理等，dingwei212@163.com；

周凱（1985-），男，講師，博士研究生，就讀于浙江工業大學信息工程學院，主要研究方向為無線網網絡建模、無線網絡容量計算、無線網絡路由設計，zhoukai@ zjut.edu.cn。

Research on Routing Algorithm in Wireless Sensor Network Based on Grover Fusion Theory*

DING Weijie1，2，ZHOU Kai3*，ZHOU Guomin1，WANG Xun1
（1.Department of Computer and Information Technology，Zhejiang Police College，Hangzhou 310053，2.College of Information and Engineering，Zhejiang University of Technology，Hangzhou 310023，China；3.College of Science，Zhejiang University of Technology，Hangzhou 310023，China）

How to guarantee high quality information transmission in the condition of resource-constrained is the fo?cus of current research on wireless sensor networks.Firstly，several key factors during transmission processing were discussed.To overcome the large calculation of the traditional multi-objects programming，Grover algorithm was ap?plied the routing selection to reduce amount of searching space.Finally，this paper proposed a D-S fusion algorithm to transform multi-factors into single object.This paper simulated the performance of this proposed algorithm.Com?pare with TOPSIS algorithm，this algorithm would prolong the life of the network and improve the time delay in the network effectively.

routing protocol；multi-objects programming；Grover algorithm；data fusion；TOPSIS

TP393

A

1004-1699（2016）09-1425-05

項目來源：國家自然科學基金重點項目（U1509219）；浙江省教育廳科研項目（Y201224395）；浙江警察學院校級科研項目（20150622）

2016-03-14修改日期：2016-04-07