傳感器網(wǎng)絡(luò)定向擴(kuò)散機(jī)制中梯度生成算法的研究

1、收稿日期 :2006-07-03基 金項(xiàng)目 :衛(wèi)星綜合信息網(wǎng)網(wǎng)絡(luò)管理技術(shù) (2003AA712032 資助 . 作者 簡(jiǎn)介 :廖先林 , 男 , 1963年 生 , 博士研究生 , 高級(jí)工程師 , 研究方向?yàn)橛?jì)算機(jī)網(wǎng)絡(luò) ; 趙林亮 , 男 , 1956年生 , 博士 , 教授 , 研究方向?yàn)?計(jì)算機(jī)網(wǎng)絡(luò)、 智能系統(tǒng) ; 王光興 , 男 , 1937年生 , 教授 , 博士生 傳感器網(wǎng)絡(luò)定向擴(kuò)散機(jī)制中梯度生成算法的研究廖先林 , 張志偉 , 門(mén)云會(huì) , 趙林亮 , 王光興(東北大學(xué) 信息科學(xué)與工程學(xué)院 , 遼寧 沈陽(yáng) 110004 E-mail:zh aolinliangise. neu. ed

2、u. cn摘要 :如何生成優(yōu)化的梯度是傳感器網(wǎng)絡(luò)定向擴(kuò)散中的一個(gè)關(guān)鍵問(wèn)題 , 本文在分析一種基本梯 度生成算法的問(wèn)題 基礎(chǔ)之上 , 利用興趣包的轉(zhuǎn) 發(fā)次數(shù)對(duì)其進(jìn)行改 進(jìn) , 設(shè)計(jì)了一 種分布式的最短路 徑梯度生成算法 . 該算法極大的 降低了鄰居節(jié)點(diǎn)間 建立“ 平 行梯度” 和“ 逆向梯度” 的概率 , 可構(gòu)建從源節(jié)點(diǎn)到 sink 節(jié)點(diǎn)的多條最短路 徑 . 仿真表 明 , 改進(jìn)的算 法可建立更為有效 的梯度 , 從 而使得定向擴(kuò)散中數(shù)據(jù)報(bào)文沿著更短的 路徑傳輸 , 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)的能量利用率更高 .關(guān) 鍵 詞 :傳感器網(wǎng)絡(luò) ; 定向擴(kuò)散 ; 梯度生成 ; 最短路徑中圖分類(lèi)號(hào) :T P 393

3、文獻(xiàn)標(biāo)識(shí)碼 :A 文 章 編 號(hào) :1000-1220(2007 10-1735-05Research on Gradients Setup Algorithm for Directed Diffusion in WSNL IA O X ian -lin , Z HA N G Z hi -w ei , M EN Yun -hui , ZHA O L in -lia ng , W A NG Guang -x ing(S chool of I nf or mation Science &E ng inee ring , N ortheastern Univ ersity , S heny

4、ang 110004, Ch ina Abstract :How to set up go od gr adients is cr ucial for directed diffusion in w ir eless senso r net wo rks. Based on t he resear ch of one ba sic g radients setup alg or ithm s pr oblem , utilizing int erest pa cket s for w arded tim es , t his paper presents a distr ibut ed sho

5、r test-path gr adients setup algo rithm for directed diffusion. T he impro ved alg or ithm g r ea tly decr eases t he pr obability tobuild " pa rallel g radients " and " rev erse g r adients ", and constr uct multiple shor test paths fr om sour ce node to sink no de . T he simula

6、 tio n result s sho w , this shor test-path gr adients setup algo rithm can set up mo re efficient gr adient s, t hen data packet s w ill be deliv ered alo ng shor ter pat hs , and dir ect ed diffusion fo r w ir eless senso r netw or ks is mor e energ y efficient . Key words :senso r netw or ks; dir

7、ected diffusion; g ra dients setup; shor test-path1引言以數(shù) 據(jù)為中心的定 向擴(kuò)散協(xié)議 (Directed Diffusio n 是 無(wú) 線(xiàn)傳感 器網(wǎng)絡(luò)中 平面路由協(xié) 議中的一項(xiàng) 重要內(nèi)容 , 它既完 成 了路由的功能 , 又提供了對(duì)應(yīng)用層的支持 , 較之其 它一些路由 協(xié) 議3, 4, 8, 它 具有良 好的 體系結(jié) 構(gòu) . 有關(guān) 仿真證 明定 向擴(kuò) 散在傳輸時(shí)延、 能量消耗等方面都有不錯(cuò)的性能 1.定向 擴(kuò)散主要包 括興趣發(fā) 布、 梯度 建立、 數(shù)據(jù)傳 輸、 路 徑 加強(qiáng)和修復(fù)等內(nèi)容 . 興趣描述了需要采集的數(shù)據(jù)的特征 , 一個(gè) 梯度至 少

8、描述了 鄰居節(jié)點(diǎn)之 間數(shù)據(jù)傳輸 的方向 . 因?yàn)槎鄠€(gè) 梯 度 可以構(gòu)建 從源節(jié)點(diǎn) (source 到網(wǎng) 關(guān)節(jié)點(diǎn) (sink 的 數(shù)據(jù)傳 輸 路徑 , 所以梯度表示了網(wǎng)絡(luò)的路徑 1. 對(duì)于一種特定類(lèi)型 的興 趣 , 一個(gè)節(jié)點(diǎn)之上可以存在多個(gè)梯度與其對(duì)應(yīng) , 這 就保證了從 這個(gè) 節(jié)點(diǎn)到 sink 節(jié)點(diǎn) 有多條 路徑來(lái) 傳輸與 這個(gè)興 趣對(duì)應(yīng) 的 數(shù)據(jù) , 這樣當(dāng)一個(gè)鄰居節(jié)點(diǎn)損壞的時(shí)候 , 仍然會(huì)有 其它的鄰居 節(jié)點(diǎn)來(lái) 傳輸數(shù)據(jù) , 所以一 個(gè)節(jié)點(diǎn)上 的多個(gè)梯度 保證了網(wǎng)絡(luò) 的 健壯性 . 同時(shí) 梯度在網(wǎng)絡(luò) 的能量利 用率方面也 起到了重要 的 作用 , 因?yàn)楹玫奶荻瓤梢詷?gòu)建較短的路徑 , 這樣在

9、 數(shù)據(jù)報(bào)文從 源節(jié)點(diǎn)傳輸?shù)骄W(wǎng)關(guān)節(jié)點(diǎn)時(shí)就會(huì)消耗較少 的能量 . 可見(jiàn) , 梯度與 網(wǎng)絡(luò)的健壯性和能量利用率都有著密切 的關(guān)系 .在定向擴(kuò)散中 , 梯度是 在興趣發(fā)布的過(guò)程中建立起來(lái)的 . 其大體過(guò)程是 , 網(wǎng)關(guān)節(jié)點(diǎn)首 先向自己的鄰居節(jié)點(diǎn)廣播興趣 . 當(dāng) 一個(gè)中間 節(jié)點(diǎn)從鄰居 節(jié)點(diǎn)收到 興趣之后 , 它會(huì)建 立指向興趣 轉(zhuǎn)發(fā)者的梯度 , 然后這個(gè)節(jié) 點(diǎn)再對(duì)興趣執(zhí)行廣播 . 這樣重復(fù)進(jìn) 行 , 興 趣報(bào)文被 廣播到整個(gè) 網(wǎng)絡(luò) . 當(dāng)廣播周期 結(jié)束之后 , 整個(gè) 網(wǎng)絡(luò)中也就建立了相應(yīng)的梯度 .在本論文中 , 將會(huì)研究 梯度生成的具體細(xì)節(jié) . 首先介紹一 種基本的梯度生成算法 , 分 析它的關(guān)鍵之處和效

10、果之后 , 將對(duì) 其構(gòu)造的 路徑過(guò)長(zhǎng)問(wèn) 題來(lái)改進(jìn) 這種基本算 法 , 設(shè) 計(jì)一種最短 路徑梯度生成 算法來(lái)建立 更為有效的 梯度 . 最后 , 利 用 ns22分別對(duì)兩種算法進(jìn)行仿真 , 并就網(wǎng)絡(luò)的性能進(jìn)行比較 .2基本梯度生成算法2. 1算法描述這個(gè)基本 的梯度生 成算法在 ns2. 29的定 向擴(kuò)散 協(xié)議中 已經(jīng)實(shí)現(xiàn) , 仿真結(jié)果表明 , 這個(gè)算法能在較短的時(shí)間內(nèi)以較少 的能量 建立比 較有效 的梯度 . 算法 的有限 狀態(tài)機(jī)描 述如圖 1(見(jiàn)下頁(yè) 所示 . 注意圖 中只標(biāo) 注了算 法中節(jié)點(diǎn) 主要狀 態(tài)間的 轉(zhuǎn)換 .首先 , sink 節(jié)點(diǎn)會(huì)生成一個(gè)興 趣報(bào)文 , 這 個(gè)興趣描述了所小 型

11、 微 型 計(jì) 算 機(jī) 系 統(tǒng) Jour nal o f Chinese Computer Systems 2007年 10月 第 10期 V ol. 28N o. 102007要查詢(xún)的數(shù)據(jù)的屬性 , 然后把興趣“ 注 入” 到網(wǎng) 絡(luò)當(dāng)中去 . 對(duì)于 sink 節(jié)點(diǎn) 而言 , 在興趣廣播 出去之后 , 它將會(huì) 等待接 收數(shù)據(jù) . 如果 sink 節(jié)點(diǎn)收到鄰居的興 趣 , 而自己 正好是這個(gè)興趣的 源 節(jié)點(diǎn) , sink 節(jié)點(diǎn)將會(huì)丟棄這個(gè)興趣報(bào)文 .圖 1基本梯度生成算法的有限狀態(tài)機(jī)描述 Fig. 1 Basic g r adients setup alg or ithm descriptionw

12、ith finite sta te machine中間 節(jié)點(diǎn)對(duì)于興 趣報(bào)文的 處理是這個(gè) 算法的關(guān) 鍵之處 . 當(dāng)中間 節(jié)點(diǎn)第一 次收到這個(gè) 興趣報(bào)文的 時(shí)候 , 它把這個(gè)興 趣 報(bào)文放置到興趣緩沖區(qū)當(dāng)中 , 建立指向興趣轉(zhuǎn)發(fā)者的梯度 , 進(jìn) 行一個(gè) 服從某個(gè) 均勻分布的 很小的隨機(jī) 延時(shí) , 延時(shí)結(jié)束后 再 把興趣報(bào)文廣播到自己的鄰居 . 在這段隨機(jī)延時(shí)的過(guò)程中 , 如 果節(jié)點(diǎn) 又一次從 其它的鄰居 收到了這個(gè) 興趣 , 那么節(jié)點(diǎn)還 會(huì) 建立梯指向轉(zhuǎn)發(fā)者的梯度 . 而當(dāng)延時(shí)完畢興趣已經(jīng)轉(zhuǎn)發(fā)之后 , 又一次收到這個(gè)興趣報(bào)文的時(shí)候 , 這個(gè)興趣報(bào)文會(huì)被丟棄 , 節(jié) 點(diǎn)不會(huì)進(jìn)行梯度的建立 . 這樣

13、可以保證對(duì)于同一種興趣 , 鄰居 節(jié)點(diǎn)之 間不會(huì)有 直接的環(huán)路 存在 , 因?yàn)猷従庸?jié) 點(diǎn)只有一個(gè) 梯 度 , 而且這個(gè) 梯度的方向 是從興趣 轉(zhuǎn)發(fā)時(shí)間晚 的節(jié)點(diǎn)指向 興 趣轉(zhuǎn)發(fā)時(shí)間早的節(jié)點(diǎn) .這樣 興趣報(bào)文就 會(huì)在整個(gè) 網(wǎng)絡(luò)當(dāng)中進(jìn) 行廣播 , 到達(dá)廣 播 域 中的每 一個(gè) 節(jié)點(diǎn) . 需要 強(qiáng)調(diào) 一點(diǎn) , 在一 次興趣 傳播 過(guò)程 當(dāng) 中 , 對(duì)于同一個(gè)興趣報(bào)文 , 每個(gè)傳感器節(jié)點(diǎn)只是轉(zhuǎn) 發(fā)一次 . 源節(jié) 點(diǎn)在產(chǎn)生數(shù) 據(jù)之后 , 如果發(fā)現(xiàn) 興趣緩沖 區(qū)中有相 應(yīng) 的興趣 , 它會(huì) 沿著與這個(gè) 興趣相對(duì) 應(yīng)的梯度所 建立的路徑 來(lái) 傳輸數(shù)據(jù) . 如果有多個(gè)梯度與這個(gè)興趣相對(duì)應(yīng) , 節(jié) 點(diǎn)可以隨機(jī)

14、選擇一 個(gè)梯度進(jìn) 行數(shù)據(jù)傳輸 , 也可 以向所有的 梯度都發(fā)送 數(shù) 據(jù) . 關(guān)于數(shù)據(jù)如何沿梯度進(jìn)行傳輸不屬于本論文研究的范圍 . 2. 2 算法分析節(jié)點(diǎn)上興趣轉(zhuǎn)發(fā)的隨機(jī)延時(shí)和中間 節(jié)點(diǎn)對(duì)一個(gè)興趣包只 轉(zhuǎn)發(fā)一次決定了該基本梯度生成算法不 會(huì)產(chǎn)生環(huán)路 , 代價(jià)小 , 不容易 在鏈路層 產(chǎn)生沖突 . 由于鄰 居節(jié)點(diǎn)之間 總是會(huì)建立 后 轉(zhuǎn)發(fā)興趣 節(jié)點(diǎn)指向先轉(zhuǎn)發(fā)興 趣節(jié)點(diǎn)的梯度 , 而且離 sink 節(jié) 點(diǎn) 越遠(yuǎn) , 轉(zhuǎn)發(fā)時(shí)間越晚的概率就越大 , 所以從整體的 梯度拓?fù)鋪?lái) 看 , 這個(gè)算法會(huì)滿(mǎn)足基本的梯度生成要求 , 整個(gè)網(wǎng) 絡(luò)會(huì)利用梯 度建立從 sour ce 指向 sink 的多條路徑 .2. 2

15、. 1環(huán)路問(wèn) 題分析前 面已經(jīng) 解釋 過(guò)在一 對(duì)鄰 居節(jié) 點(diǎn)之間 只能 存在 一個(gè) 梯 度 . 對(duì)于兩個(gè)鄰居 , 節(jié)點(diǎn) C 和節(jié)點(diǎn) D, 如果存在從 C 指向 D 的 C D ,那么 , 兩個(gè)節(jié)點(diǎn)對(duì)興趣的轉(zhuǎn) 發(fā)時(shí)間 (節(jié)點(diǎn) C 要晚 :T (C >T (D . 假設(shè)在節(jié)點(diǎn) A 和節(jié)點(diǎn) B 之間存在環(huán)路 , 那么就有 :A X B Y A對(duì)于興趣的轉(zhuǎn)發(fā)時(shí)間 , 也就 有 :T (A >T (X > >T (B >T (Y > >T (A 所以 :T (A >T (A 顯然 , 這是矛盾 的 . 所 以我們的假 設(shè)是錯(cuò)誤 的 , 所 以使用 這種基本

16、的梯度生成算法 , 在一次興趣傳播的過(guò)程當(dāng)中 , 任意 的兩個(gè)傳感器節(jié)點(diǎn)之間不會(huì)形成環(huán)路 .2. 2. 2能量消耗分析對(duì)無(wú)線(xiàn)傳感器網(wǎng)絡(luò)而言 , 特別是對(duì)于大規(guī)模的網(wǎng)絡(luò) , 將興 趣報(bào)文廣 播到整個(gè)網(wǎng) 絡(luò)當(dāng)中去 是一個(gè)很大 的能量消耗 . 但在 不知道 網(wǎng)絡(luò) 中哪個(gè) 節(jié)點(diǎn) 會(huì)采集 到與 興趣對(duì) 應(yīng)的 數(shù)據(jù) 的情況 下 , 這又是唯一的一種選擇 . 有關(guān)研究是利用地理位置對(duì)興趣 的廣播進(jìn) 行控制 , 但現(xiàn)在還 沒(méi)有廉價(jià)而 又準(zhǔn)確的 方法來(lái)獲取 無(wú)線(xiàn)傳感器網(wǎng)絡(luò)節(jié)點(diǎn)的地理位置 . 在這個(gè)算法當(dāng)中 , 每個(gè)節(jié)點(diǎn) 對(duì)于同一 個(gè)興趣報(bào)文 只是轉(zhuǎn)發(fā) 一次 , 所 以興趣報(bào) 文被轉(zhuǎn)發(fā)的 次數(shù)等于網(wǎng)絡(luò)中廣播域的節(jié)

17、點(diǎn)個(gè)數(shù) . 這種情況下 , 能量消耗相 對(duì)較小 .2. 2. 3媒體接入層的沖突避免傳感器網(wǎng) 絡(luò)使用的 是無(wú)線(xiàn)通信 方式 , 無(wú)線(xiàn)通信過(guò) 程中進(jìn) 行沖突檢測(cè)是 一件困難的事情 , 所以在進(jìn) 行無(wú)線(xiàn) ma c 設(shè)計(jì)的 時(shí)候經(jīng)常 采用的策 略是沖突避 免和一些 調(diào)度機(jī) 制 5. 傳感器 網(wǎng)絡(luò)上三 層在進(jìn)行分 布式協(xié)議 設(shè)計(jì)的時(shí)候 , 應(yīng)該 考慮避免數(shù) 據(jù)報(bào)文在 mac 層發(fā)生沖突 , 也就是鄰居 節(jié)點(diǎn)盡量 避免在同一 時(shí)刻發(fā)送 數(shù)據(jù) . 這 個(gè)算法利 用興趣報(bào)文 的隨機(jī)延 時(shí)轉(zhuǎn)發(fā)來(lái)避 免廣播 過(guò)程中 興趣報(bào) 文在 mac 層 發(fā)生 沖突 . 如圖 2所 示 , 當(dāng) 節(jié)點(diǎn) 0把 興趣報(bào)文廣 播之后

18、, 節(jié)點(diǎn) 1和 節(jié)點(diǎn) 2幾乎 會(huì)同時(shí)收 到這個(gè)興趣報(bào)文 , 如果節(jié)點(diǎn) 1和節(jié)點(diǎn) 不進(jìn)行隨機(jī)的延時(shí) , 而是 直接將興 趣轉(zhuǎn)發(fā)出去 , 那么 興趣報(bào)文將 會(huì)有很大 的可能性在 兩者的共 同鄰居節(jié) 點(diǎn) 3上面發(fā) 生沖突 , 導(dǎo)致節(jié)點(diǎn) 3接收不到 興趣報(bào)文 .圖 2節(jié)點(diǎn)無(wú)延時(shí)興趣轉(zhuǎn)發(fā)沖突 示意圖 Fig. 2 Illustr atio n o f collision o n no de w ithno time delay to pro pag ate int er est在這個(gè)算法當(dāng)中 , 隨機(jī) 延時(shí)服從一個(gè)從 0到 0. 05秒的均 勻分布 . 假設(shè)興 趣報(bào)文的大 小是 50字節(jié) , 無(wú)線(xiàn)信道數(shù)

19、 據(jù)傳輸 速率是 1M /S . 經(jīng)過(guò)計(jì) 算 , 如果使 用了 隨機(jī) 延時(shí) , 圖 2中在節(jié) 點(diǎn) 3上面 發(fā)生興趣 報(bào)文沖突 的概率 是 1. 6%.如果 ma c 層使 , , 1736 小型微型計(jì)算機(jī)系統(tǒng) 2007年個(gè) 更 小 的 CT S 報(bào) 文 , 這 樣 發(fā) 生 沖 突 的 概 率 更 是 會(huì) 小 于 1. 6%.所 以如果我們使用了隨 機(jī)延時(shí) , 在 真實(shí)網(wǎng)絡(luò)中發(fā)生 廣 播沖突的概率很小 .2. 2. 4梯度拓 撲結(jié)果由于 隨機(jī)延時(shí)的 存在 , 生成的梯度 拓?fù)涞慕Y(jié) 果也就帶 有 隨機(jī)性 . 利用 上述算法形 成的梯度 拓?fù)涞闹饕?特征是鄰居 節(jié) 點(diǎn) 之 間 必 然 存 在 單 向

20、 的 梯 度 , 而 且 整 體 的 梯 度 走 向 是 從 source 節(jié)點(diǎn)指向 sink 節(jié)點(diǎn) , 這已經(jīng) 符合定向擴(kuò) 散梯度建立 的 要求 .基本的梯度生成算法存在的問(wèn)題之 一是這個(gè)算法沒(méi)有解 決過(guò)長(zhǎng)路徑的問(wèn)題 . 在接下來(lái)的部分中 , 我們會(huì)對(duì) 這個(gè)基本算 法進(jìn)行改進(jìn) , 來(lái)生成一個(gè)更為優(yōu)化的梯度拓?fù)?.3最短路徑梯度生成算法為了 使得數(shù)據(jù)報(bào) 文在傳輸 過(guò)程中消耗 的能量最 少 , 我 們 改進(jìn)基 本的梯度 生成算法 , 設(shè)計(jì)了 這種最短路 徑梯度生成 算 法 , 來(lái)生成可構(gòu)建最短路徑的梯度 .3. 1 問(wèn)題分析 :平行梯度和逆向梯度為了 保證傳輸數(shù) 據(jù)報(bào)文消 耗的能量最 少 , 那

21、 就要保證 從 源節(jié)點(diǎn)到 sink 節(jié)點(diǎn)的路徑最 短 , 那么就 應(yīng)該保證節(jié)點(diǎn)上的 每 個(gè)梯度都 是最優(yōu)的 , 每個(gè)梯度構(gòu)建的路 徑都是通往 sink 節(jié) 點(diǎn) 的 最短 路 徑 . 也可 以說(shuō) , 經(jīng) 過(guò) 一個(gè) 梯 度 , 數(shù)據(jù) 報(bào) 文 就越 接 近 sink , 反之 , 梯度的存在就會(huì)過(guò)多消耗網(wǎng)絡(luò)的能量 .在利 用基本的梯度生成 算法得到的梯度拓 撲圖 3(a 中 , 因?yàn)楣?jié)點(diǎn) 1可以直接把數(shù)據(jù)報(bào) 文轉(zhuǎn)發(fā)給 sink 節(jié)點(diǎn) , 而無(wú)須 再 用節(jié) 點(diǎn) 3進(jìn)行轉(zhuǎn) 發(fā) , 所以 從節(jié)點(diǎn) 1指 向節(jié)點(diǎn) 3的 梯度是多 余 的 . 因?yàn)?這兩個(gè)節(jié) 點(diǎn)距離 sink 節(jié) 點(diǎn)的跳數(shù) 值是 一樣的 , 所

22、 以 這兩個(gè) 節(jié)點(diǎn)間的 梯度會(huì)浪費(fèi) 網(wǎng)絡(luò)的能量 , 稱(chēng)具 有相同跳數(shù) 值 的節(jié)點(diǎn)間的梯度為平行梯度 . 這種平行梯度是應(yīng)該去掉的 .(a 平行梯度和逆向梯度 , 興趣轉(zhuǎn)發(fā)時(shí)間 :節(jié)點(diǎn) 3<節(jié)點(diǎn) 1<節(jié)點(diǎn) 4<節(jié)點(diǎn) 2(b 最優(yōu)梯度拓?fù)?圖 3一般梯度拓?fù)渑c最優(yōu)梯度拓?fù)?F ig . 3 Gener al g radients to po lo g y w ithbest g radients to po lo gy更為嚴(yán)重的情況是梯度從具有跳數(shù) 值小的節(jié)點(diǎn)指向了跳 數(shù)值 大的節(jié)點(diǎn) , 例 如圖 3(a 中的從節(jié)點(diǎn) 2指向 節(jié)點(diǎn) 4的梯 度 就是這種情況 , 如果節(jié)點(diǎn) 2使用這

23、個(gè)梯度來(lái)發(fā)送數(shù)據(jù)報(bào)文 , 那 么至少要 經(jīng)過(guò)多余的兩跳才 能把數(shù)據(jù)報(bào)文發(fā)送 到 sink 節(jié)點(diǎn) . 在 圖 3(a 拓?fù)渲?, 如果 使用基 本的梯 度建立算 法 , 節(jié)點(diǎn) 2將 會(huì)有 16. 67%的概率 擁有指向 節(jié)點(diǎn) 4的梯 度 . 我們稱(chēng) 這種 完 全背離 sink 節(jié)點(diǎn)方向、 從跳數(shù)值小的節(jié) 點(diǎn)指向跳數(shù)值大的 節(jié) .在新的算法當(dāng) 中 , 我們認(rèn) 為可以構(gòu)建從源節(jié) 點(diǎn)到 sink 節(jié) 點(diǎn)的最短 路徑的梯度 是最優(yōu)的 梯度 , 并 以此為標(biāo) 準(zhǔn)來(lái)生成梯 度 . 在一次興趣廣播的過(guò)程 中 , 如果一個(gè)中間節(jié)點(diǎn)對(duì)興趣報(bào)文 進(jìn)行了轉(zhuǎn)發(fā) , 那么這個(gè)節(jié)點(diǎn) 就是正常的節(jié)點(diǎn) , 包括能量和鏈路 狀況

24、 , 我們可以使用這個(gè)節(jié) 點(diǎn)來(lái)發(fā)送數(shù)據(jù) . 盡管在興趣失效之 前節(jié)點(diǎn)可 能壞掉 , 然而通過(guò) 興趣的周期 性廣播可 以使得這個(gè) 損壞節(jié)點(diǎn)在下一次興趣傳播過(guò)程中被忽視 . 所以 , 我們認(rèn)為可 以構(gòu)建 從源節(jié) 點(diǎn)到 sink 節(jié)點(diǎn)的 最短路 徑的梯 度可以 使得網(wǎng) 絡(luò)使用最 少的能量來(lái) 進(jìn)行數(shù)據(jù) 傳送 , 并 且認(rèn)為這 種梯度是最 好的梯度 . 圖 3(b 是最佳梯度的一個(gè)拓?fù)涫疽?.接下來(lái) , 我們將 會(huì)改進(jìn)基本 算法來(lái)降 低在梯度生 成過(guò)程 中建立平 行梯度和逆 向梯度的 概率 , 從 而得到一 個(gè)更為接近 于最優(yōu)化結(jié)果的梯度拓?fù)?, 使得網(wǎng)絡(luò)的能量利用率更高 . 我們 稱(chēng)這個(gè)改 進(jìn)的算法為

25、 最短路徑 梯度生成算 法 , 因 為這個(gè)算法 可以確立從源節(jié)點(diǎn)到 sink 節(jié)點(diǎn)的多條最短路徑 . 3. 2使用興趣報(bào)文的轉(zhuǎn)發(fā)次數(shù)改進(jìn) 基本算法平行梯度和逆向梯度存在的根本原因是基本算法只是利 用興趣報(bào) 文轉(zhuǎn)發(fā)時(shí)間 的早晚來(lái) 確定梯度方 向 , 而 這個(gè)算法卻 不能完全 保證離 sink 節(jié)點(diǎn)遠(yuǎn)的 節(jié)點(diǎn)總是會(huì) 先于離 sink 節(jié)點(diǎn) 近的節(jié)點(diǎn)晚一些轉(zhuǎn)發(fā)興趣報(bào)文 , 如圖 3(a.解決 的方法 是使 用興 趣報(bào)文 的轉(zhuǎn) 發(fā)次數(shù) 來(lái)修 改基 本算 法 . 對(duì)每一種興趣 , 節(jié)點(diǎn)設(shè)置一個(gè)稱(chēng)為節(jié)點(diǎn)跳數(shù)的變量與其對(duì) 應(yīng) , 并利用 節(jié)點(diǎn) 收到 的興趣 報(bào)文 的轉(zhuǎn)發(fā) 次數(shù) 對(duì)其進(jìn) 行更 新 . Sink

26、 節(jié)點(diǎn)的節(jié)點(diǎn)跳數(shù)是 0.當(dāng)一 個(gè)中間 節(jié)點(diǎn) 第一 次收到 某種 類(lèi)型的 興趣 報(bào)文 的時(shí) 候 , 它會(huì)將興趣報(bào)文放置到 興趣緩沖區(qū)當(dāng)中 , 建立指向興趣轉(zhuǎn) 發(fā)者的 梯度 , 并利 用興趣報(bào) 文的轉(zhuǎn)發(fā)次 數(shù)來(lái)初始 化本節(jié)點(diǎn)與FT :興趣報(bào)文轉(zhuǎn)發(fā)次數(shù) NH :節(jié)點(diǎn)跳數(shù)值 RS :興趣報(bào)文是否轉(zhuǎn)發(fā)圖 4新算法興趣報(bào)文處理流程F ig . 4 Options on the new r eceived inter est pa cket 這種興趣對(duì)應(yīng)的節(jié)點(diǎn)跳數(shù) , 然后準(zhǔn)備進(jìn)行延時(shí)轉(zhuǎn)發(fā) . 如果節(jié)點(diǎn) , 173710期 廖先林 等 :傳感器網(wǎng)絡(luò)定 向擴(kuò)散機(jī)制中梯度生成算法的研究 己的節(jié) 點(diǎn)跳數(shù)值 與興趣

27、報(bào)文 里面的轉(zhuǎn)發(fā) 次數(shù)進(jìn)行 比較 . 如 果 轉(zhuǎn)發(fā)次 數(shù)小于節(jié) 點(diǎn)跳數(shù) , 那么這個(gè) 節(jié)點(diǎn)將會(huì)刪 除以前建立 的 關(guān)于這種興趣的所有梯度 , 建立新的指向這個(gè)轉(zhuǎn)發(fā)者的梯度 , 使用這 個(gè)更小的 興趣報(bào)文的 轉(zhuǎn)發(fā)次數(shù)更 新它的節(jié) 點(diǎn)跳數(shù) . 如 果此時(shí) 節(jié)點(diǎn)還沒(méi) 有把興趣報(bào) 文轉(zhuǎn)發(fā)出去 , 那么 還要用這個(gè) 興趣報(bào)文的轉(zhuǎn)發(fā)次數(shù)加一來(lái)更新待轉(zhuǎn)發(fā)的 興趣報(bào)文的轉(zhuǎn)發(fā)次數(shù) 值 . 如果轉(zhuǎn)發(fā)次數(shù)跟節(jié)點(diǎn)跳數(shù)值相等 , 那么節(jié)點(diǎn)只 是添加一個(gè) 新的 梯度 . 如 果轉(zhuǎn)發(fā)次 數(shù)大 , 那 么這個(gè)興 趣報(bào)文將會(huì) 被丟棄 . 注意的 是不論節(jié) 點(diǎn)將興趣報(bào) 文轉(zhuǎn)發(fā)與否 , 節(jié)點(diǎn) 都會(huì)進(jìn)行上 面 的比較和操作 . 圖

28、4(見(jiàn)上 頁(yè) 說(shuō)明 了新算 法對(duì) 于興趣 報(bào)文 的 處理流程 .3. 3 算法分析改 進(jìn)的算 法利 用了興 趣報(bào) 文的 轉(zhuǎn)發(fā)次 數(shù)來(lái) 去掉 平行 梯 度、 修 改逆向 梯度 . 舉例來(lái) 說(shuō) , 在 圖 3(a 中 , 盡 管節(jié) 點(diǎn) 4比 節(jié) 點(diǎn) 2要 早一些轉(zhuǎn) 發(fā)興趣報(bào)文 , 但是 節(jié)點(diǎn) 2不會(huì) 建立指向節(jié) 點(diǎn) 4的梯度 , 因?yàn)楣?jié)點(diǎn) 2會(huì)發(fā)現(xiàn)它的節(jié) 點(diǎn)跳數(shù) (本圖中是 1 要小 于節(jié) 點(diǎn) 4發(fā)送來(lái)的興趣報(bào) 文的轉(zhuǎn)發(fā)次數(shù) (本圖中是 3. 相反 , 節(jié)點(diǎn) 4會(huì)建 立指向 節(jié)點(diǎn) 2的 梯度 , 盡管節(jié) 點(diǎn) 4在 收到節(jié) 點(diǎn) 2轉(zhuǎn)發(fā)來(lái)的興趣報(bào)文的時(shí)候節(jié)點(diǎn) 4已經(jīng)進(jìn)行過(guò)了興 趣報(bào)文的轉(zhuǎn) 發(fā) , 因?yàn)?/p>

29、興趣報(bào)文里面的轉(zhuǎn)發(fā)次數(shù)等于節(jié)點(diǎn)的跳數(shù)值 , 本圖中 都是 2. 這樣的比較和操作 會(huì)極大的去除平行 梯度 , 修改逆 向 梯度 , 使得局部的梯度更為合理 , 最終會(huì)得到一個(gè) 接近于最佳 梯度的梯度拓?fù)?.注意 的是我們還 是不能完 全得到最優(yōu) 化的梯度 , 因?yàn)?中 間節(jié)點(diǎn)只能轉(zhuǎn)發(fā)一次興趣報(bào)文 , 所以關(guān)于自己的跳數(shù)值 , 它可 能對(duì)自己的鄰居“ 說(shuō)謊” . 我 們的算 法還是一 種盡最 大努力 的 情況 (best -effor t case , 我們所能保證的就是每個(gè)節(jié)點(diǎn)只是保 留指向“ 看起來(lái)” 具有 最小跳數(shù) 值節(jié)點(diǎn) 的梯度 . 在下 面的仿 真 部分中 , 我們 將會(huì)看到新 算法對(duì)

30、于 梯度的建立 結(jié)果有了很 大 的改進(jìn) .4仿真我們 用 ns-2進(jìn) 行新協(xié) 議設(shè)計(jì) 6, 7, 實(shí) 現(xiàn)了 最短路 徑梯 度 生 成算法 , 并 進(jìn)行了 仿真 . 我 們的仿 真工 作主要 包括 兩個(gè) 方 面 , 一個(gè)是關(guān)于梯度生成結(jié)果的分析 , 一個(gè)是關(guān)于 整個(gè)網(wǎng)絡(luò)節(jié) 能效果的分析 .4. 1 梯度生成結(jié)果分析首 先 , 我 們?cè)O(shè)計(jì) 了一 個(gè)集中 式的 算法 (一 個(gè)用 java 來(lái) 實(shí) 現(xiàn)的寬度優(yōu)先搜索算法 來(lái)計(jì)算理想的最佳梯度拓?fù)?, 這個(gè)最 佳的梯度 拓?fù)浒◤脑垂?jié)點(diǎn) 到 sink 節(jié)點(diǎn)的所有 最短路徑 . 然 后分別使用基本的梯度生成算法和最短 路徑梯度生成算法進(jìn) 行仿 真 , 在仿

31、 真過(guò)程中 提取各個(gè)中 間節(jié)點(diǎn)上面 的梯度 . 最后 , 用仿真結(jié)果與最佳結(jié)果進(jìn)行比較 .為了便于比較 , 特進(jìn)行如下的定義 . 如果一個(gè) 梯度出現(xiàn)在 仿真結(jié)果集中 , 同時(shí)也出現(xiàn)在理想最佳梯度集中 , 我們稱(chēng)之為 一 個(gè)命中 (HI T , 如 果一個(gè) 梯度出 現(xiàn)在仿真 結(jié)果集 中而沒(méi) 有 在 最佳結(jié)果集 中 , 我 們稱(chēng)之為一 個(gè)錯(cuò)誤 (ERRO R , 另外一 種 情況 是一個(gè) 梯度 在最 佳梯度 集中 而沒(méi)有 出現(xiàn) 在仿真 結(jié)果 集 中 , ( 路徑 , 而錯(cuò)誤會(huì)使得網(wǎng)絡(luò)使 用過(guò)多的能量來(lái)傳輸數(shù)據(jù)報(bào)文 . 所 以命中數(shù)量越多越好 , 而錯(cuò) 誤和丟失越少越好 .我們用不同規(guī)模大小的傳感器

32、網(wǎng)絡(luò)來(lái)進(jìn)行仿真 , 從 50個(gè) 節(jié)點(diǎn)到 250個(gè)節(jié) 點(diǎn) . 50個(gè)節(jié)點(diǎn) 的場(chǎng)地 是隨 機(jī)的把 50個(gè)節(jié)點(diǎn) 放 置在長(zhǎng) 和寬都 是 800米 的場(chǎng)地中 . 每個(gè)傳感 器節(jié)點(diǎn) 的通信圖 5一個(gè)改進(jìn)算法的梯度拓?fù)浣Y(jié)果Fig. 5 O ne g r adient s t opolog y r esults w ithimpro ved alg or ithm半徑是 250米 (我 們采用了 802. 11協(xié)議 的默認(rèn) 通信半 徑 , 對(duì) 于 W SN 可 能大了 一點(diǎn) , 但這不 影響仿 真比較 . 其它 大小的 場(chǎng)地 , 包 括 100個(gè)節(jié)點(diǎn)、 150個(gè)節(jié)點(diǎn)、 200個(gè)節(jié)點(diǎn)、 250個(gè) 節(jié)點(diǎn) , 分

33、別通過(guò) 調(diào)整場(chǎng)地的 大小來(lái)保 持節(jié)點(diǎn)的密 度不變 . 在每種大 小的場(chǎng)地上仿真都進(jìn)行兩次 , 分別采用不同的梯度生成算法 , 基本的梯 度生成算 法和最短路 徑梯度生成 算法 . 圖 5是一個(gè) 使用了最短路 徑梯度生成算法的 梯度拓?fù)浣Y(jié)果 (使用 jav a 繪 制 , 圖 6是兩種算法梯度生成結(jié)果的一個(gè)比較 .(a 梯度命中個(gè)數(shù)比較(a Co mpariso n of g radients HIT numbers(b 梯度錯(cuò)誤個(gè)數(shù)比 較(b Co mpa riso n o f g radients ERRO R numbers 圖 6兩種算法梯度生成結(jié)果 比較F ig. 6 Co mpar

34、iso n o f gr adients set up r esultsw ith tw o alg or ithms從圖 6的 比較中可以 看出 , 最短路徑生 成算法有 更多的 命中和很 明顯更少的 錯(cuò)誤 , 這就說(shuō)明使 用了最短 路徑梯度生1738 小型微型計(jì)算機(jī)系統(tǒng) 2007年能量 節(jié)省來(lái)說(shuō)是 很重要的 , 在 4. 2中 我們將會(huì) 看到最短路 徑 梯度生 成算法的 這個(gè)優(yōu)勢(shì)會(huì) 使得網(wǎng)絡(luò)更 節(jié)能 . 需要解釋的 一 點(diǎn)是 , 與基本算法相比較 , 最短路徑梯度生成算法 會(huì)有更多的 丟失 , 但是丟失一般是發(fā)生在有多個(gè)梯度存在的節(jié)點(diǎn)上的 , 所 以某幾個(gè)最佳梯度的丟失對(duì)網(wǎng)絡(luò)性能的 影響不

35、大 .4. 2 網(wǎng)絡(luò)能量利用率的提高在這 一部分 , 我們將會(huì) 比較基本算 法和最短 梯度生成 算 法 在網(wǎng)絡(luò) 能耗 方面的 表現(xiàn) . 在 ns2. 29實(shí)現(xiàn) 的定 向擴(kuò) 散協(xié) 議 中 , 在路 徑加 強(qiáng)之前 , 數(shù) 據(jù)是 按照隨 機(jī)選 擇的梯 度進(jìn) 行傳 輸 的 . 如果一個(gè)節(jié)點(diǎn)上的梯度都是最佳的 , 那么數(shù)據(jù) 報(bào)文將會(huì)總 是沿著 最短的路 徑進(jìn)行傳輸 , 這樣 整個(gè)網(wǎng)絡(luò)就 會(huì)使用更少 的 能量 . 我們使用兩個(gè)標(biāo)準(zhǔn)來(lái)評(píng)價(jià)網(wǎng)絡(luò)的能量利用情況 :總的數(shù) 據(jù)報(bào)文轉(zhuǎn)發(fā)次數(shù)和總的網(wǎng)絡(luò)能量消耗 .sink 節(jié)點(diǎn)在 0. 14秒 進(jìn)行興趣的廣播 , 當(dāng)源節(jié)點(diǎn)接收 到興 趣的時(shí)候 它會(huì)以恒定的速率 進(jìn)行數(shù)

36、據(jù)回傳 . 為了保證 sink 節(jié) 點(diǎn)和源節(jié) 點(diǎn)之間是多跳傳輸 , 我們將 sink 節(jié)點(diǎn)和源節(jié)點(diǎn)放 置 在網(wǎng)絡(luò)的兩端 . 因?yàn)樵垂?jié)點(diǎn)是以恒定的速率產(chǎn)生數(shù)據(jù)的 , 那么 在恒 定的仿真時(shí) 間內(nèi) , sink 節(jié)點(diǎn)所收 到的數(shù)據(jù)報(bào) 文的個(gè)數(shù) 幾 乎是一 樣的 . 所以整個(gè)網(wǎng) 絡(luò)進(jìn)行總 的數(shù)據(jù)報(bào)文 的轉(zhuǎn)發(fā)次數(shù) 越 少 , 整個(gè)網(wǎng)絡(luò) 就會(huì)利用較 少的能量 來(lái)傳遞相同 的有效的數(shù) 據(jù) 報(bào)文 , 網(wǎng)絡(luò)的能量利用率就越高 . 比較結(jié)果如圖 7所示 .(a 數(shù)據(jù)報(bào)文的總轉(zhuǎn)發(fā)次數(shù)比 較 (a Compar ison of data packets re-sent times(b 總能量消耗比較(b Co mp

37、ar iso n o f tot al ener gy co st圖 7兩種算法能量消耗比較F ig. 7 Compar ison of ener gy co st w ith tw o alg or ithms 因?yàn)楦倪M(jìn)的算法有更高的概率使得 數(shù)據(jù)報(bào)文沿著最短的 路徑進(jìn) 行傳輸 , 所以它很 大的降低 了總的數(shù)據(jù) 報(bào)文的轉(zhuǎn)發(fā) 次 數(shù) , 如圖 7(a 所示 , 這樣就使得網(wǎng)絡(luò) 消耗了更少的 能量 , 如 圖 7(b 所示 . 從圖 7(b 可以看出 , 250個(gè)節(jié)點(diǎn)的網(wǎng)絡(luò) 的節(jié)能效果 沒(méi)有 200個(gè)節(jié)點(diǎn)的網(wǎng) 絡(luò)的節(jié)能 效果好 . 這是因?yàn)?網(wǎng)絡(luò)的規(guī) 模 越大 , 網(wǎng)絡(luò)的興趣廣播能量消耗越大

38、. 特別是當(dāng)數(shù) 據(jù)傳輸速率 很低而 興趣廣播 的頻率較高 的情況下 , 興趣廣 播的能耗將 會(huì) . 網(wǎng)絡(luò)定向 擴(kuò)散協(xié)議的 一個(gè)關(guān)鍵 點(diǎn) , 這個(gè) 問(wèn)題應(yīng)該 進(jìn)行進(jìn)一步 的研究 .5結(jié)論為了使得 無(wú)線(xiàn)傳感 器網(wǎng)絡(luò)的定 向擴(kuò)散更 簡(jiǎn)單有效 , 我們 設(shè)計(jì)了這 種最短路徑 梯度生成 算法 . 這 個(gè)算法是 在基本的梯 度生成算 法的基礎(chǔ)之 上 , 利 用興趣報(bào)文 的轉(zhuǎn)發(fā)次 數(shù)來(lái)去掉平 行梯度、 修改逆向梯度 , 最終得到了一個(gè)更接近于最優(yōu)結(jié)果的 梯度拓?fù)?, 這個(gè)結(jié)果幾乎包 括從源節(jié)點(diǎn)到 sink 節(jié)點(diǎn)的所有最 短路徑 . 仿真結(jié)果表明 , 梯度建立結(jié)果已經(jīng)相當(dāng)接近于最優(yōu)化 的結(jié)果 , 數(shù)據(jù)報(bào)文的傳

39、輸會(huì) 沿著更短的路徑進(jìn)行 , 整個(gè)網(wǎng)絡(luò)的 能量利用率更高 .我們下一步的工作是研究如何利用已生成的最短路徑梯 度來(lái)進(jìn)一步簡(jiǎn)化和改進(jìn)定向擴(kuò)散的其它步驟 . 例如 , 我們可以 考慮去掉 路徑加強(qiáng)的 步驟 , 因?yàn)槭褂米?短路徑梯 度生成算法 之后 , 所有的路 徑都是最佳 的 , 這 樣會(huì)使得協(xié) 議更為簡(jiǎn) 單 . 不 過(guò)需要注 意的是 , 最短路徑 梯度生成算 法犧牲了 一定的網(wǎng)絡(luò) 的健壯性 來(lái)獲得更高 的能量利 用率 , 所 以關(guān)于網(wǎng) 絡(luò)的健壯性 研究也是我們下一步工作的一個(gè)重點(diǎn) . References :1C halerm ek Intanagon wiw at, Rames h Govindan , Deborah Es-trin, et al. Directed diffusion for w ireless s ens or n etw orking C . IEEE/ACM T rans actions on Netw orkin g, Novemb er, 2003:2-16.2NS-2Netw ork Simu lator EB/OL . http:/w ww. is