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

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

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

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

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

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

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

路由協(xié)議；多目標(biāo)規(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é)點(diǎn)構(gòu)成，并實(shí)現(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ò)研究的熱點(diǎn)領(lǐng)域之一。由于傳統(tǒng)的分布式路由協(xié)議以網(wǎng)絡(luò)節(jié)點(diǎn)為中心，造成網(wǎng)絡(luò)節(jié)點(diǎn)計(jì)算量都較大，且無線傳感網(wǎng)絡(luò)的布網(wǎng)環(huán)境較有線網(wǎng)絡(luò)更為惡劣，許多網(wǎng)絡(luò)資源受到制約（如網(wǎng)絡(luò)中節(jié)點(diǎn)的能量有限）［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é)點(diǎn)能量消耗、網(wǎng)絡(luò)傳輸時(shí)延、分組丟失率等等）。因此，如何在網(wǎng)絡(luò)資源受限時(shí)，提供高質(zhì)量的信息服務(wù)顯得更為重要。有相關(guān)文獻(xiàn)指出［3］：當(dāng)路由選擇時(shí)的約束條件包含兩個(gè)或者兩個(gè)以上參數(shù)組合時(shí)，該路由問題便是一個(gè)NP完全問題，即多項(xiàng)式復(fù)雜程度的非確定性問題，該問題無法使用傳統(tǒng)的算法就行求解。國內(nèi)外的專家也針對這個(gè)問題展開了一些研究。如文獻(xiàn)［4］提出利用串聯(lián)排隊(duì)的方法，降低網(wǎng)絡(luò)路由的搜索量，實(shí)現(xiàn)網(wǎng)絡(luò)中信息傳輸?shù)姆?wù)質(zhì)量保障。文獻(xiàn)［5］對最重要的幾個(gè)因素Top-k服務(wù)組合進(jìn)行建模，采用啟發(fā)式算法（貪婪算法）縮小求解空間，從而實(shí)現(xiàn)網(wǎng)絡(luò)中信息傳輸?shù)姆?wù)質(zhì)量保障。

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

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

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

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

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

圖1　一階能量消耗模型

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

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

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

其中，Ei（t）表示節(jié)點(diǎn)i在當(dāng)前時(shí)刻的剩余能量；Ej（t）表示節(jié)點(diǎn)j在當(dāng)前時(shí)刻的剩余能量。

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

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

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

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

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

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

根據(jù)被測概率等于振幅的平方，滿足振幅的平方和等于1的條件。因?yàn)椴僮骶仃嚥皇菃挝痪仃?，所以得到的概率矢量需要進(jìn)行歸一化處理。歸一化以后，鏈路基于能量選擇的概率和基于時(shí)延選擇的概率表達(dá)如下：

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

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

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

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

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

圖2　兩種路由策略計(jì)算量對比圖

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

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

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

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

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

4　結(jié)束語

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

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

［6］郝曉辰，竇晶晶，劉彬.基于路徑損耗的無線傳感器網(wǎng)絡(luò)分布式拓?fù)淇刂扑惴ǎ跩］.軟件學(xué)報(bào).2009，20（12）：3213-3222.

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

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

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

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