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

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

基于Grover融合理論的無線傳感網(wǎng)絡(luò)路由算法研究*

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

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

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

路由協(xié)議；多目標規(guī)劃；Grover算法；數(shù)據(jù)融合；TOPSIS

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

無線傳感器網(wǎng)絡(luò)WSN（Wireless Sensor Net?work）是一種由大量可自組織形成多跳無線網(wǎng)絡(luò)的傳感節(jié)點構(gòu)成，并實現(xiàn)信息處理與傳輸?shù)男滦途W(wǎng)絡(luò)。由于無線傳感網(wǎng)絡(luò)組網(wǎng)靈活，不受現(xiàn)有基礎(chǔ)設(shè)備約束等優(yōu)勢，因而被廣泛地應(yīng)用于軍事、醫(yī)療等領(lǐng)域中［1］，引起了國內(nèi)外學(xué)者的廣泛關(guān)注。其中，網(wǎng)絡(luò)路由協(xié)議就是無線傳感網(wǎng)絡(luò)研究的熱點領(lǐng)域之一。由于傳統(tǒng)的分布式路由協(xié)議以網(wǎng)絡(luò)節(jié)點為中心，造成網(wǎng)絡(luò)節(jié)點計算量都較大，且無線傳感網(wǎng)絡(luò)的布網(wǎng)環(huán)境較有線網(wǎng)絡(luò)更為惡劣，許多網(wǎng)絡(luò)資源受到制約（如網(wǎng)絡(luò)中節(jié)點的能量有限）［2］，因此傳統(tǒng)的路由協(xié)議并不適用于無線傳感網(wǎng)絡(luò)。探索一種能夠在資源受限的情況，確保高質(zhì)量信息傳輸?shù)穆酚蓞f(xié)議顯得尤為重要。

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

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

1　網(wǎng)絡(luò)關(guān)鍵參數(shù)計算方法

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

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

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

圖1　一階能量消耗模型

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

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

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

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

當僅考慮節(jié)點剩余能量進行路由選擇時，優(yōu)先選擇剩余能量較高的鏈路進行信息轉(zhuǎn)發(fā)。因此每一條路的被選擇概率與該條鏈路的剩余能量成正比。

2　Grover融合多目標路由數(shù)學(xué)模型

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

對于一個N節(jié)點構(gòu)成的無線傳感網(wǎng)絡(luò)將會形成N2條可能的鏈路。整個網(wǎng)絡(luò)維護著兩個N2×N2鏈路操作矩陣

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

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

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

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

3　網(wǎng)絡(luò)仿真

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

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

在如上的無線傳感網(wǎng)絡(luò)環(huán)境中，進行1 225次的業(yè)務(wù)量仿真，對比兩種算法在計算量上的性能差異，部分效果如圖2所示。

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

從圖2可以發(fā)現(xiàn)：對于相同的業(yè)務(wù)請求，兩種協(xié)議在路由搜索過程中，Grover融合路由算法在網(wǎng)絡(luò)計算量上普遍低于由DSR-TOPSIS路由協(xié)議所產(chǎn)生的計算量?？梢?，Grover算法的確可以有效地降低由多目標規(guī)劃問題產(chǎn)生的高計算量問題。

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

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

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

圖4　兩種算法下網(wǎng)絡(luò)業(yè)務(wù)傳輸時延變化圖

4　結(jié)束語

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

［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自動服務(wù)組合方法［J］.電子學(xué)報，2012，40（7）：1489-1491.

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

［7］姜向遠，張煥水，王偉.一種基于非完全數(shù)據(jù)的路徑損耗模型選擇算法［J］.電子與信息學(xué)報，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網(wǎng)絡(luò)組播端到端時延建模與優(yōu)化［J］.計算機學(xué)報，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-）男，河南西平人，浙江警察學(xué)院計算機與信息技術(shù)系講師，浙江工業(yè)大學(xué)信息工程學(xué)院博士研究生。主要研究方向為信號處理，計算機網(wǎng)絡(luò)建模，圖像處理等，dingwei212@163.com；

周凱（1985-），男，講師，博士研究生，就讀于浙江工業(yè)大學(xué)信息工程學(xué)院，主要研究方向為無線網(wǎng)網(wǎng)絡(luò)建模、無線網(wǎng)絡(luò)容量計算、無線網(wǎng)絡(luò)路由設(shè)計，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

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

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