一種有效的稀疏無線傳感器網絡路由方案

宋朝，鄭迎鳳，趙文彬

（1.黃河科技學院現代教育技術中心，河南 鄭州 450000；2.石家莊鐵道大學信息科學與技術學院，河北 石家莊 050043）

一種有效的稀疏無線傳感器網絡路由方案

宋朝1，鄭迎鳳1，趙文彬2

（1.黃河科技學院現代教育技術中心，河南 鄭州 450000；2.石家莊鐵道大學信息科學與技術學院，河北 石家莊 050043）

稀疏無線傳感器網絡中節點之間距離過遠，使得移動代理節點成為最有效的數據收集方式，然而移動代理節點由于能量限制無法在一次數據收集中到達網絡所有節點進行數據收集。為保證在能量受限的移動代理節點總路由路徑最短，給出了一種稀疏無線傳感器網絡能量受限移動代理節點的路由方案。 首先構建移動代理節點的路由數學模型，然后根據移動代理節點初始能量將無線傳感器網絡劃分成不同的子集，最后采用旅行商人問題的模擬退火算法計算出每個子集最短路由，全部子路由的集合即最優路由。 仿真及其分析結果表明：隨著網絡節點個數增多和移動代理節點能量增大，所給方案的總路由能夠比較接近于理想情況，在實際應用中比較有效且適于推廣。

稀疏無線傳感器網絡；移動代理節點；旅行商人問題；路由算法

1 引言

當 前 ，無 線 傳 感 器 網 絡 （wireless sensor network，WSN）被廣泛用于戰場監視、環境監測、交通監控醫療監察等各種關鍵應用領域中。無線傳感器網絡中所有傳感器節點將收集的數據信息傳送到基站進行處理分析，所以數據收集的路由選擇問題成為無線傳感器網絡的研究熱點。傳統的路由解決方法主要采用多跳路由技術，但是由于稀疏無線傳感器網絡節點之間的距離較遠，使得多跳路由技術不能在稀疏無線傳感器網絡中使用。而移動代理節點方式由于方便、靈活、高效，被認為是稀疏無線傳感器網絡中比較有效 的 數 據 收 集 方 法［1，2］。根 據 應 用 環 境 （公 路 、河 流 、管 道 等 ）不同，車輛、船舶等都能作為移動代理節點載體。由于部署傳感器節點的區域大多是較為偏遠且環境比較惡劣的地域，尤其是在稀疏無線傳感器網絡（比如公路交通監管）中，傳感器節點分布比較分散而且無法互相通信，車輛或陸用機器人有可能在崎嶇的山路上或者斷壁懸崖前無法前進到 指 定 的 區 域 ，所 以 無 人 飛 行 器 （unmanned aerial vehicle，UAV）能夠很好地作為移動代理節點的載體應用在大多數條件較為惡劣的環境中。并且無人飛行器所攜帶的燃料和電池是受限的，經過一段時間的工作后需重返基站補充各種能源，因此關于移動代理節點如何選擇路由才能更高效快捷已成為稀疏無線傳感器網絡研究的熱點問 題［3，4］。

假設移動代理節點在理想狀態下的各種能量都是充足的，僅在一次數據收集時間內就能夠到達部署區域的所有傳感器節點，這時可將該問題轉化為旅行商人問題（traveling salesman problem，TSP），應 用 模 擬 退 火 （simulated annealing，SA）算 法［5］即 能 計 算 得 到 移 動 代 理 節 點 的 最 優 路由。但移動代理節點在實際狀態下能量是有限的，需要在基站和節點之間進行多次往返補充能量，且因無人飛行器等移動代理節點使用代價較高，使得在網絡中部署許多個無人飛行器不現實。本文在考慮到移動代理節點能量有限的基礎上，給出一種稀疏無線傳感器網絡中能量有限移動代 理 節 點 的 路 由 方 案 （routing scheme of energy-constrained mobileagentnodein sparsewirelesssensornetwork，E-CMAN）。所給方案首先構建出在相關約束條件下的數學模型，其次利用旅行商人問題解決方法根據移動代理節點的限制能量大小將全網絡劃分為若干個子集，并在每個子集中采用模擬退火算法計算出最優的子路由，最后將全部子路由組集合即形成最優總路由，且所得到的路由非常接近于理想狀態下的路由，能較好地適用在對時間不敏感的稀疏無線傳感器網絡中。

2 相關研究

在稀疏無線傳感器網絡中，利用移動代理節點實施數據收集的方法已成為國內外學者研究的重點，提出了針對不 同 情 況 下 的 移 動 代 理 節 點 路 由 問 題［6，7］。Tariq 等 人［8］設 計移動代理節點在傳感器節點部署區域內隨機移動，且以一定的概率進行數據收集，這種方案的數據收集效率不高且無 法 保 證 收 集 到 所 有 節 點 數 據 信 息 。Jeonghwa 等 人［9］設 計 當移動代理節點能量消耗殆盡，網絡中某一成員節點將會轉化為移動代理節點繼續進行數據收集，該方案要求網絡中傳感器節點能夠移動，這有可能造成區域數據感知缺失，從而影響整個網絡的穩定性，而且由于節點更換比較困難這將 會 增 加 該 方 案 實 施 的 復 雜 性 。Almi’ani等 人［10］設 計 了 在 移動代理節點能量有限時進行數據收集所需的最長路由，并使用多跳路由和移動代理節點路由的混合路由方式，首先是根據移動代理節點的初始能量將全網絡分成許多個獨立的簇，即簇的個數與移動代理節點的初始能量有關，同時選舉簇頭進行預先數據收集，然后移動代理節點僅收集簇頭節點的數據，該方案需要各節點之間可以相互通信，但這將會導致簇頭節點的能耗過快，從而影響全網絡壽命 。彭 偉 等 人［11］主 要 是 在 考 慮 時 間 敏 感 性 的 情 況 下 ，根 據控制消息時延來確定最少的移動代理節點數目，該方案能夠滿足對時間敏感度要求較高的網絡，但是對于一些非時間敏感度的網絡則無疑提升了成本。現有的方案大多是考慮在某一特定環境中的路由選擇方法，與所給E-CMAN 方案適用 的應用環境存在一定 的 差別，其中所 給E-CMAN 方 案 的 網 絡 應 用 環 境 可 見 于 第 3 節 中 的 網 絡 模型介紹。

3 網絡模型

E-CMAN 方案 的應用 環 境 主要具備 下 述 4 個特 性 ：在部署范圍內所有節點與基站均不能移動，所在坐標一經確定就保持不變；節點之間、節點和基站之間均不能互相通信與信息傳輸，這是因為所有節點都被高度分散部署在較大區域范圍內；移動代理節點的初始能源和電池是有限的，只能支持一段距離的路程，然后需返回基站進行補充后才能繼續工作；全網絡是非時間敏感度的，為了降低成本僅使用一個移動代理節點，并且依照預設路徑實施數據收集。下面給出應用網絡環境與移動代理節點的相關假設：

· 節點使用較低的數據采集速率，且其所采集的數據在傳送給移動代理節點前不會失效；

· 移動代理節點擁有足夠大的存儲緩沖區，能收集網絡覆范圍內所有節點數據信息且不會溢出；

·移動代理節點需到達節點指定位置才可收集數據，不需考慮節點的傳輸距離和方向；

·移動代理節點在轉向時的時間和能耗開銷能夠忽略不計；

·移動代理節點等待某一節點傳輸數據過程中的時間和能耗開銷同其移動距離所需的時間和能耗開銷相比能夠忽略不計；

· 移動代理節點在返回基站后，所需能源和電池會自動重新補裝填滿。

4 E-CMAN 算法設計

4.1 數學模型

E-CMAN 方案的 主要思想 ：首 先 將全網絡 分 為 獨立的許多個不同子集，各個子集的節點個數應滿足移動代理節點的自身能量限制，其次計算移動代理節點在各個子集中的最優子路由，移動代理節點多次往返后到達各個子集中所有傳感器節點形成的路由集合即為最優的路由方案，其中移動代理節點的往返次數與劃分子集的數目相同。假設S 表 示 稀 疏無線 傳 感 器網絡，包括 N 個 節 點 ，令 s0表 示 基站 ，si表 示 某 一 節 點 ，且 有 i=1，2，… ，N，其 坐 標 表 示 為 （xi，yi），則 兩 個 節 點 sa與 sb間 的 距 離 長 度 是 d（sa，sb）=假定整個稀疏無線傳感器網絡被分成M 個子集，各個子集包含有 Nq個節點，令 Si表 示第 q 個子集 ，spq表 示 第 q 個 子 集 中 的 第 p 個 節 點 ，且 有 q=1，2，… ，M，p=1，2，… ，Nt。由 于 移 動 代 理 節 點 在 各 個 子 集 中 往 返 一 次 均需 要 兩 次 返 回 基 站 ，因 此 令和分 別 表 示 基 站 在 每 個子集代表的出發節點和到達節點。令 F為移動代理節點在其有限能量狀態下所能行進的最長距離，從而可以將能量限制轉換成距離限制，以便能夠更直觀地構建數學模型。式（1）給出了移動代理節點的最優總路由表示：

其中，式（1）具有以下約束條件：

（1）Nq≥1，能夠確保各個子集均不為空；

（2）Su∩Sυ= ，1≤u≠ υ≤M ， 能 夠 確 保 一 個 節 點 僅包含在一個子集中，即移動代理節點僅訪問每個節點一次；

（5）F≥2d（s0，si），1≤i≤N，確 保 移 動 代 理 節 點 的 能 量 足夠從基站到最遠節點之間往返一次，能避免移動代理節點因能量過少而不能進行數據收集；

（6）M＜N，能夠確保在稀疏無線傳感器網絡中至少有兩個以上的子集，若 T=N，該模型會退化為移動代理節點每次往返僅能訪問一個節點。

4.2 最優路由算法

E-CMAN 算法包括 兩 個 步驟：根據移 動 代理節點 自 身能量限制，對全網絡實施子集劃分；在各個子集內應用旅行商人問題求解方法計算出各個子集的最優子路由，所有最優子路由組成的集合即為整個稀疏無線傳感器網絡的最優總路由。算法1給出了網絡子集劃分算法。在子集的劃分過程中，要先在假設移動代理節點自身能量為無限大時 ，應 用 TSP 求 解 算 法［12］計 算 出 子 集 中 的 路 由 節 點 序 列 ，并 令 表 示 RTSP此 節 點 序 列 ，然 后 依 次 計 算 節 點 序 列 之 間 的距離，在小于或等于限制距離 F的序列長度內所包含的節 點 表 示 為 一 個 子 集 。 令 RTSP表 示 在 不 受 能 量 限 制 時 利用 模 擬 退 火 算 法 計 算 出 的 路 由 ，MTSP表 示 路 由 RTSP中 具有 的 傳 感 器 節 點 個 數 ，Rtemporary表 示 當 前 的 臨 時 路 由 ，Rsubset表示移動代理節點在自身能量限制內行進的最長子路徑，Ssubset=Compute（Rsubset）表 示 計 算 路 徑 Rsubset中 具 有 的 傳 感 器 節點個數。

算法1 子集劃分算法

輸 入 ：S，F，s0；

輸出：Sq。

當 i≤MTSP時，則 重 復 執 行 ：

若 i=MTSP，則 跳 出 此 循 環 ；／說 明 移 動 代 理 節 點具有足夠的能量遍歷全網絡中所有傳感器節點，則此時跳出該循環

在 算 法 1 中 ，因 子 路 徑 Rsubset是 沿 RTSP的 路 徑 行 進 的 ，但 RTSP是 在 沒 有 能 量 限 制 時 計 算 出 來 的 ，所 以 在 劃 分 為 子集 后 ，子 路 徑 Rsubset并 不 一 定 是 子 集 Sq中 的 最 優 子 路 由 。同時需要說明的是，算法 1的主要作用是將整個網絡劃分為相互獨立的不同子集區域，移動代理節點在劃分過程中僅遍歷每個傳感器節點一次，即使在算法 1的網絡劃分過程中存在路徑相交的情況，但每個傳感器節點仍分屬不同的子集網絡中，由于移動代理節點每次完成一個子集的數據收集后將會返回基站重新補充能量，然后繼續進行下一個子集的數據收集，所以算法1的子集劃分過程不會影響此后的最優子集路徑計算。在實施網絡子集劃分后，對每個子集再次采用旅行商問題解決方法計算出移動代理節點在各個子集中的路由才是最優子路由，而全部子路由的集合即是網絡最優總路由。算法 2給出了網絡最優路由算法。由算法 1可知 ，網絡被 分成 M 個子集且每個子集含有 Nq個節點，同時要注意各個子 集 內 均 有 兩 個 s0， 即 Sq=s0→spq→s0，1 ≤j≤Nq。 其 中Rsubroute=TSP（Sq）表 示 應 用 模 擬 退 火 算 法 計 算 出 子 集 Sq而 得到的最優子路由。

算法2 最優路由算法

輸入：Sq，F，s0；

輸 出 ：Roptimal。

對于 q從 1到 M，重復執行：

5 算法性能分析

假設稀疏無線傳感器網絡部署在二維平面區域內，覆蓋 面 積 10 km×10 km，基 站 坐 標 為 （0，0），移 動 代 理 節 點 的初 始 能 量 允 許 能 夠 工 作 的 最 長 距 離 為 F=30 km。 利 用MATLAB R2006a 仿 真 環 境 ，圖 1 給 出 了 當 稀 疏 無 線 傳 感器網絡節點為 10 個時，采用所給 E-CMAN 算法 得到的路由示意。可以看出，整個網絡被分為兩個子集，分別包含 6個和 4 個 節點（除基站 外 ），且兩 個子 集 的 面 積 基 本 相 似，說明移動代理節點每一次在子集內的數據收集都最大化且均衡地利用了自身有限的能量和燃料。

圖1 E-CMAN 算 法 在 節點個數為 10 時的路由

在稀疏無線傳感器網絡中，移動代理節點的路由主要同節點個數和能量大小有關。圖2和圖3分別給出了移動代理節點的總路由隨著節點個數增加和限制能量增大時的變 化 情 況 ，同 時 分 別 同 理 想 情 況 下［13］的 路 由 Rideal、最 近 鄰 居 節點 查 找 算 法［14］的 路 由 Rneighbor及 旅 行 商 人 問 題 求 解 算 法［15］的 路 由 RTSP進 行 了 分 析 比 較 。由 圖 2 可 以 看 出 ，隨 著 網 絡節點的個數增多，移動代理節點在 4種算法下的路由長度均是增大的，這是因為移動代理節點的能量是既定的，隨著節點增加使得子集的數目也在增多，進而移動代理節點需往返基站的次數也要增多，從而增大了總路由 的 長 度 。然 而 E-CMAN 算法的路由增加幅度總體較小，且比較接近于 理想狀態 下 的 路由長度 。另外，E-CMAN 算法在同樣的節點個數下與其他 3種算法相比，總路由的長度最短。

圖2 隨著網絡節點個數增加總路由的變化

圖3 隨著移動代理節點限制能量增大總路由的變化

由圖3可以看出，隨著移動代理節點的限制能量增大，4 種算法下的移動代理節點 路由長度均 是減少 的，主要是因為移動代理節點的能量增大將會減少子集的個數，從而使移動代理節點往返基站的次數減少，因而總路由的長度也在減少。然而，根據 E-CMAN 算法計算所得路由減少的幅度更大，更加接近于理想狀態下的路由。且E-CMAN 算法在同樣的能量限制條件下，與 其 余 3 種 算 法的 路 由 長 度 相 比 ，其 總 路 由長 度 是 最 短 的 。另 外 ，圖 3 的橫 坐 標 從 30 km 處 開 始 ， 這 表 示 移 動 代 理 節 點 自 身 能量可以支持其一次往返節點和基站的最短距離，假如移動代理節點初始能量所能支持的工作距離小于該距離，則該移動代理節點就不能執行這個網絡的數據收集工作。

6 結束語

因稀疏無線傳感器網絡中的傳感器節點數量比較少，可將移動代理節點訪問每個傳感器節點的路由問題看作旅行商人問題。但因移動代理節點自身能量存在限制，使得其不能一次完成整個網絡中傳感器節點的數據收集。所以，本文給出了一種稀疏無線傳感器網絡中能量有限移動代理節點的路由方案，通過將全網絡劃分為移動代理節點，可以一次全部訪問許多個子集區域，然后對各個子集利用旅行商人問題求解方法計算出各個子路由，最終全部子路由的集合即最優總路由。性能分析結果表明，E-CMAN算法隨網絡規模的增加與限制能量的增大均比較接近于理想狀態下的路由，非常適用于實際應用，具有很好的研究和推廣價值。

［1］ 湯文俊，張國良，曾靜，等. 一種適用于稀疏 無線傳感 器網 絡 的改 進 分 布 式 UIF 算 法［J］.自動化學報，2014，40（11）：2490-2498. TANG W J，ZHANG G L，ZENG J，et al.An improved distributed unscented information filter algorithm for sparse wireless sensor networks［J］.Acta Automatica Sinica，2014，40（11）：2490-2498.

［2］ 苗 勇 ，崔 莉. 稀 疏 無 線 傳 感 器 網 絡 移 動 節 點 定 位 算 法 ［J］. 高技 術 通 訊，2010，20（5）：454-460. MIAO Y ，CUI L.A mobile node localization method for sparse mobile wireless sensornetworks ［J］.Chinese High Technology Letters，2010，20（5）：454-460.

［3］ 孫 子 文 ，劉 加 杰 ，紀 志 成. 無 線 傳 感 器 網 絡 中 基 于 代 理 的D-S 數 據 融 合 ［J］. 計 算 機 工 程 與 科 學 ，2014，36 （10）：1919-1924. SUN Z W，LIU J J，JI Z C.Agent based D-S data fusion in wireless sensor networks［J］.Computer Engineering and Science，2014，36（10）：1919-1924.

［4］ 趙輝，賈 宗璞. 基 于移 動輔 助 的 無 線 傳 感 器 網 絡 信 息 獲 取 技術 研 究 ［J］. 計 算 機 應 用 研 究 ，2014，31（11）：3447-3454. ZHAO H，JIA Z P.Mobile assisted wireless sensor network information acquisition technique ［J］.Application Research of Computers，2014，31（11）：3447-3454.

［5］ 李 忠. 采 用 遺 傳 模 擬 退 火 策 略 的 WSN 節 點 部 署 優 化 ［J］. 系 統仿 真 學 報，2014，26（2）：353-356. LI Z.Application research of computers deployment of wireless sensor network nodes by improved genetic simulated annealing algorithm ［J］.Journal of System Simulation，2014，26 （2）：353-356.

［6］ 張 勝，楊 鄭 龍，曹 凱 英. 基 于 移 動 agent的 能 量 平 衡 環 形 路 由算 法 ［J］. 計 算 機 應 用 研 究 ，2014，31（9）：2661-2664. ZHANG S，YANG Z L，CAO K Y.Energy balanced ring routing algorithm based on mobile agent ［J］.Application Research of Computers，2014，31（9）：2661-2664.

［7］ 楊 鄭 龍 ，張 勝，吳 卉. 基 于 移 動 agent的 能 量 平 衡 螺 旋 形 路 由算 法 ［J］. 傳 感 器 與 微 系 統 ，2014，33（10）：128-132. YANG Z L，ZHANG S，WU H.Energy balanced spiral routing algorithm based on mobile agent ［J］. Transducer and Microsystem Technologies，2014，33（10）：128-132.

［8］ TARIQ M M B，ZEGURA M A，ZEGURA E.Message ferry route design for sparse ad hoc networks with mobile nodes ［C］／／The 7th ACM International Symposium on Mobile Ad Hoc Networking and Computing，May 22-25，2006，Florence，Italy. New York：ACM Press，2006：37-48.

［9］ JEONGHWA Y，YAND C，AMMAR M，et al.Ferry replacement protocols in sparse MANET message ferrying systems ［C］／／Wireless Communications and Networking Conference，March 13-17，2005，New Orleans，USA.New Jersey：IEEE Press，2005：2038-2044.

［10 ］ALMI’ ANI K ，VIGALS A ，LIBMAN L.Energy-efficient datagathering with tourlength-constrained mobile elementsin wireless sensor networks ［C］／2010 IEEE 35th Conference on Local Computer Networks （LCN），Oct 10-14，2010，Denver，USA.New Jersery：IEEE Press，2010：582-589.

［11］PENG W，ZHAO B K，YU W R，et al.Ferry route design with delay bounds in delay-tolerant networks ［C］／The 2010 IEEE 10th International Comference on Computer and Information Technology （CIT），June 29- July 1，2010，Bradford，UK.New York：IEEE Press，2010：281-288.

［12］ZHENG J G，WU D Q，ZHOU L.Traveling salesman problem using an enhanced hybrid swarm optimization algorithm ［J］. Journal of Donghua University （English Edition），2014，31 （3）：362-367.

［13］IBM.ILOG CPLEX Optimizer［EB／OL］.［2015-06-20］.http：／www-01. ibm.com／software／integra- tion／optimization／cplex-optimizer／.

［14］LONG J，GUI W H.Node deployment strategy optimization forwireless sensor network with mobile basestation ［J］. Journal of Central South University of Technology，2012，19（2）：453-458.

［15］Helsgaun K.IKH ［EB／OL］. ［2015-06-20］.http：／www.akira.ruc. dk／～keld／reaserch／LKH／.

An effective routing scheme of sparse wireless sensor networks

SONG Chao1，ZHENG Yingfeng1，ZHAO Wenbin2
1.Modern Educational Technology Center，Huanghe Science and Technology College，Zhengzhou 450000， China 2.College of Information Science and Technology，Shijiazhuang Railway University，Shijiazhuang 050043，China

Mobile agent node has become the most efficiency way of data collection in sparse wireless sensor networks，because the distance of the nodes is too far.However，the mobile agent node could not access all the nodes to gather the data in a routing travel because of energy-constrained.In order to make the energy-constrained mobile agent node obtain the minimum total route，an effective routing scheme of energy-constrained mobile agent node in sparse wireless sensor networks was presented.The mathematic model of the route of mobile agent node was built firstly，and then the whole wireless sensor network was split into different subsets according to the energy of the mobile agent node.Then the shortest routes were computed by adopting simulated annealing of traveling salesman problem.Finally，the obtained total route of sub-routes was the optimal route.The analysis results of simulation and performance show that the total route of the presented scheme is close to the ideal situation along with the increase of the number of nodes and the raise of the energy of mobile agent node.So the presented scheme is very effective in the practice and is propitious to popularize.

sparse wireless sensor network，mobile agent node，traveling salesman problem，routing algorithm

The National Natural Science Foundation of China（No.61232008）

TP393

：A

10.11959／j.issn.1000-0801.2016094

宋 朝 （1983-）， 男 ， 黃 河 科 技 學 院 現 代 教 育技術中心講師，主要研究方向為計算機應用、信息安全。

鄭 迎 鳳 （1984-）， 女 ， 黃 河 科 技 學 院 現 代 教育技術中心講師，主要研究方向為計算機應用、信息安全。

趙文彬（1985-），男 ，博 士 ，石 家 莊 鐵 道 大 學信息科學與技術學院講師，主要研究方向為科學可視化、復雜網絡和信息安全。

2015-07-01；

2016-03-08

國 家 自 然 科 學 基 金 資 助 項 目 （No.61232008）