宋朝，鄭迎鳳，趙文彬

（1.黃河科技學(xué)院現(xiàn)代教育技術(shù)中心，河南 鄭州 450000；2.石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043）

一種有效的稀疏無(wú)線傳感器網(wǎng)絡(luò)路由方案

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

（1.黃河科技學(xué)院現(xiàn)代教育技術(shù)中心，河南 鄭州 450000；2.石家莊鐵道大學(xué)信息科學(xué)與技術(shù)學(xué)院，河北 石家莊 050043）

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

稀疏無(wú)線傳感器網(wǎng)絡(luò)；移動(dòng)代理節(jié)點(diǎn)；旅行商人問(wèn)題；路由算法

1 引言

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

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

2 相關(guān)研究

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

3 網(wǎng)絡(luò)模型

E-CMAN 方案 的應(yīng)用 環(huán) 境 主要具備 下 述 4 個(gè)特 性 ：在部署范圍內(nèi)所有節(jié)點(diǎn)與基站均不能移動(dòng)，所在坐標(biāo)一經(jīng)確定就保持不變；節(jié)點(diǎn)之間、節(jié)點(diǎn)和基站之間均不能互相通信與信息傳輸，這是因?yàn)樗泄?jié)點(diǎn)都被高度分散部署在較大區(qū)域范圍內(nèi)；移動(dòng)代理節(jié)點(diǎn)的初始能源和電池是有限的，只能支持一段距離的路程，然后需返回基站進(jìn)行補(bǔ)充后才能繼續(xù)工作；全網(wǎng)絡(luò)是非時(shí)間敏感度的，為了降低成本僅使用一個(gè)移動(dòng)代理節(jié)點(diǎn)，并且依照預(yù)設(shè)路徑實(shí)施數(shù)據(jù)收集。下面給出應(yīng)用網(wǎng)絡(luò)環(huán)境與移動(dòng)代理節(jié)點(diǎn)的相關(guān)假設(shè)：

· 節(jié)點(diǎn)使用較低的數(shù)據(jù)采集速率，且其所采集的數(shù)據(jù)在傳送給移動(dòng)代理節(jié)點(diǎn)前不會(huì)失效；

· 移動(dòng)代理節(jié)點(diǎn)擁有足夠大的存儲(chǔ)緩沖區(qū)，能收集網(wǎng)絡(luò)覆范圍內(nèi)所有節(jié)點(diǎn)數(shù)據(jù)信息且不會(huì)溢出；

·移動(dòng)代理節(jié)點(diǎn)需到達(dá)節(jié)點(diǎn)指定位置才可收集數(shù)據(jù)，不需考慮節(jié)點(diǎn)的傳輸距離和方向；

·移動(dòng)代理節(jié)點(diǎn)在轉(zhuǎn)向時(shí)的時(shí)間和能耗開(kāi)銷(xiāo)能夠忽略不計(jì)；

·移動(dòng)代理節(jié)點(diǎn)等待某一節(jié)點(diǎn)傳輸數(shù)據(jù)過(guò)程中的時(shí)間和能耗開(kāi)銷(xiāo)同其移動(dòng)距離所需的時(shí)間和能耗開(kāi)銷(xiāo)相比能夠忽略不計(jì)；

· 移動(dòng)代理節(jié)點(diǎn)在返回基站后，所需能源和電池會(huì)自動(dòng)重新補(bǔ)裝填滿。

4 E-CMAN 算法設(shè)計(jì)

4.1 數(shù)學(xué)模型

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

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

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

（2）Su∩Sυ= ，1≤u≠ υ≤M ， 能 夠 確 保 一 個(gè) 節(jié) 點(diǎn) 僅包含在一個(gè)子集中，即移動(dòng)代理節(jié)點(diǎn)僅訪問(wèn)每個(gè)節(jié)點(diǎn)一次；

（5）F≥2d（s0，si），1≤i≤N，確 保 移 動(dòng) 代 理 節(jié) 點(diǎn) 的 能 量 足夠從基站到最遠(yuǎn)節(jié)點(diǎn)之間往返一次，能避免移動(dòng)代理節(jié)點(diǎn)因能量過(guò)少而不能進(jìn)行數(shù)據(jù)收集；

（6）M＜N，能夠確保在稀疏無(wú)線傳感器網(wǎng)絡(luò)中至少有兩個(gè)以上的子集，若 T=N，該模型會(huì)退化為移動(dòng)代理節(jié)點(diǎn)每次往返僅能訪問(wèn)一個(gè)節(jié)點(diǎn)。

4.2 最優(yōu)路由算法

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

算法1 子集劃分算法

輸 入 ：S，F(xiàn)，s0；

輸出：Sq。

當(dāng) i≤MTSP時(shí)，則 重 復(fù) 執(zhí) 行 ：

若 i=MTSP，則 跳 出 此 循 環(huán) ；／說(shuō) 明 移 動(dòng) 代 理 節(jié) 點(diǎn)具有足夠的能量遍歷全網(wǎng)絡(luò)中所有傳感器節(jié)點(diǎn)，則此時(shí)跳出該循環(huán)

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

算法2 最優(yōu)路由算法

輸入：Sq，F(xiàn)，s0；

輸 出 ：Roptimal。

對(duì)于 q從 1到 M，重復(fù)執(zhí)行：

5 算法性能分析

假設(shè)稀疏無(wú)線傳感器網(wǎng)絡(luò)部署在二維平面區(qū)域內(nèi)，覆蓋 面 積 10 km×10 km，基 站 坐 標(biāo) 為 （0，0），移 動(dòng) 代 理 節(jié) 點(diǎn) 的初 始 能 量 允 許 能 夠 工 作 的 最 長(zhǎng) 距 離 為 F=30 km。 利 用MATLAB R2006a 仿 真 環(huán) 境 ，圖 1 給 出 了 當(dāng) 稀 疏 無(wú) 線 傳 感器網(wǎng)絡(luò)節(jié)點(diǎn)為 10 個(gè)時(shí)，采用所給 E-CMAN 算法 得到的路由示意?？梢钥闯?，整個(gè)網(wǎng)絡(luò)被分為兩個(gè)子集，分別包含 6個(gè)和 4 個(gè) 節(jié)點(diǎn)（除基站 外 ），且兩 個(gè)子 集 的 面 積 基 本 相 似，說(shuō)明移動(dòng)代理節(jié)點(diǎn)每一次在子集內(nèi)的數(shù)據(jù)收集都最大化且均衡地利用了自身有限的能量和燃料。

圖1 E-CMAN 算 法 在 節(jié)點(diǎn)個(gè)數(shù)為 10 時(shí)的路由

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

圖2 隨著網(wǎng)絡(luò)節(jié)點(diǎn)個(gè)數(shù)增加總路由的變化

圖3 隨著移動(dòng)代理節(jié)點(diǎn)限制能量增大總路由的變化

由圖3可以看出，隨著移動(dòng)代理節(jié)點(diǎn)的限制能量增大，4 種算法下的移動(dòng)代理節(jié)點(diǎn) 路由長(zhǎng)度均 是減少 的，主要是因?yàn)橐苿?dòng)代理節(jié)點(diǎn)的能量增大將會(huì)減少子集的個(gè)數(shù)，從而使移動(dòng)代理節(jié)點(diǎn)往返基站的次數(shù)減少，因而總路由的長(zhǎng)度也在減少。然而，根據(jù) E-CMAN 算法計(jì)算所得路由減少的幅度更大，更加接近于理想狀態(tài)下的路由。且E-CMAN 算法在同樣的能量限制條件下，與 其 余 3 種 算 法的 路 由 長(zhǎng) 度 相 比 ，其 總 路 由長(zhǎng) 度 是 最 短 的 。另 外 ，圖 3 的橫 坐 標(biāo) 從 30 km 處 開(kāi) 始 ， 這 表 示 移 動(dòng) 代 理 節(jié) 點(diǎn) 自 身 能量可以支持其一次往返節(jié)點(diǎn)和基站的最短距離，假如移動(dòng)代理節(jié)點(diǎn)初始能量所能支持的工作距離小于該距離，則該移動(dòng)代理節(jié)點(diǎn)就不能執(zhí)行這個(gè)網(wǎng)絡(luò)的數(shù)據(jù)收集工作。

6 結(jié)束語(yǔ)

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

［1］ 湯文俊，張國(guó)良，曾靜，等. 一種適用于稀疏 無(wú)線傳感 器網(wǎng) 絡(luò) 的改 進(jìn) 分 布 式 UIF 算 法［J］.自動(dòng)化學(xué)報(bào)，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］ 苗 勇 ，崔 莉. 稀 疏 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 移 動(dòng) 節(jié) 點(diǎn) 定 位 算 法 ［J］. 高技 術(shù) 通 訊，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］ 孫 子 文 ，劉 加 杰 ，紀(jì) 志 成. 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 中 基 于 代 理 的D-S 數(shù) 據(jù) 融 合 ［J］. 計(jì) 算 機(jī) 工 程 與 科 學(xué) ，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］ 趙輝，賈 宗璞. 基 于移 動(dòng)輔 助 的 無(wú) 線 傳 感 器 網(wǎng) 絡(luò) 信 息 獲 取 技術(shù) 研 究 ［J］. 計(jì) 算 機(jī) 應(yīng) 用 研 究 ，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 節(jié) 點(diǎn) 部 署 優(yōu) 化 ［J］. 系 統(tǒng)仿 真 學(xué) 報(bào)，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］ 張 勝，楊 鄭 龍，曹 凱 英. 基 于 移 動(dòng) agent的 能 量 平 衡 環(huán) 形 路 由算 法 ［J］. 計(jì) 算 機(jī) 應(yīng) 用 研 究 ，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］ 楊 鄭 龍 ，張 勝，吳 卉. 基 于 移 動(dòng) agent的 能 量 平 衡 螺 旋 形 路 由算 法 ［J］. 傳 感 器 與 微 系 統(tǒng) ，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，F(xiàn)lorence，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-）， 男 ， 黃 河 科 技 學(xué) 院 現(xiàn) 代 教 育技術(shù)中心講師，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用、信息安全。

鄭 迎 鳳 （1984-）， 女 ， 黃 河 科 技 學(xué) 院 現(xiàn) 代 教育技術(shù)中心講師，主要研究方向?yàn)橛?jì)算機(jī)應(yīng)用、信息安全。

趙文彬（1985-），男 ，博 士 ，石 家 莊 鐵 道 大 學(xué)信息科學(xué)與技術(shù)學(xué)院講師，主要研究方向?yàn)榭茖W(xué)可視化、復(fù)雜網(wǎng)絡(luò)和信息安全。

2015-07-01；

2016-03-08

國(guó) 家 自 然 科 學(xué) 基 金 資 助 項(xiàng) 目 （No.61232008）