【導讀】路由協(xié)議不能有效地用于無線傳感器網(wǎng)絡。本文分析了無線傳感器網(wǎng)絡的特。由協(xié)議的分析和研究得出了一些有用的結論。最后對無線傳感器網(wǎng)絡未來的研。究策略與發(fā)展趨勢進行了展望。教師的指導下進行的研究工作及取得的成果。盡我所知，除文中特。位或?qū)W歷而使用過的材料。對本研究提供過幫助和做出過貢獻的個。人或集體，均已在文中作了明確的說明并表示了謝意。文的部分或全部內(nèi)容。研究所取得的研究成果。除了文中特別加以標注引用的內(nèi)容外，本。論文不包含任何其他個人或集體已經(jīng)發(fā)表或撰寫的成果作品。本人完全意識到本聲明的法律后果由本人承擔。版，允許論文被查閱和借閱。本人授權大學可以將。影印、縮印或掃描等復制手段保存和匯編本學位論文。涉密論文按學校規(guī)定處理。

　　

【正文】 控制以及負載平衡 機 制。為實現(xiàn) 上 述 目 標， SPEED 協(xié)議首先交換節(jié)點的傳輸 延 遲，以得到網(wǎng)絡負載情況； 然后節(jié)點利用局部地理信息和傳輸速率信息作出路 由決定，同時通過鄰居反饋機制保證網(wǎng)絡傳輸速率在 — 個全局定義的傳輸速率閾 值之上。節(jié)點還通過反向 壓 力路 由 變更機制避開延遲太大的鏈路和路 由空洞。 SPEED 協(xié)議主要 由 以下幾部分組成： (1)延遲估計機制，用來得到網(wǎng)絡的負載情況，判斷網(wǎng)絡是否發(fā) 生 擁塞； (2) SNGF 算法 ，用來選 擇滿足傳 輸 速率要求的下一跳節(jié)點； (3)鄰居反饋策略 (NFL)是當 SNGF 路 由 算法中找不到滿足傳輸速率要求的下一跳節(jié)點時采取的補償機制； (4) 反向壓力路由變更機制，用來避免擁塞和路由空 洞。 SPEED 協(xié)議中各部分之間的關系如圖 32 所示。 25 圖 32 SPEED 協(xié)議框架 能量感知路由 能量路由 能量路 由 是最早提出的傳感器網(wǎng) 絡路由機制之一，所以本文將重點分析和探討它。能量路由 根據(jù)節(jié)點的可用能量 (power available ,PA)或傳輸路徑上的能量需求，選擇數(shù)據(jù)的轉(zhuǎn)發(fā)路徑。 節(jié) 點可用能量就是節(jié)點 當前的剩余能量。 圖 33 所示的網(wǎng)絡 中 ，大寫字母表示節(jié)點，如節(jié)點 A， 節(jié)點右側括號內(nèi)的數(shù)字表 示 節(jié)點的可用能量。圖中的雙向線表 示 節(jié)點之間的通信鏈路，鏈路 上 的數(shù)字 表示 在該鏈路上發(fā)送數(shù)據(jù)消耗的能量。源節(jié)點是一般功能的傳感器節(jié)點，完成數(shù)據(jù)采集工作。 匯 聚節(jié)點是數(shù)據(jù)發(fā)送的目標節(jié)點。 在 圖 33 中，從源節(jié)點到匯聚節(jié)點的可能路徑有： 路徑 1：源節(jié)點 — B— A— 匯聚 節(jié) 點，路徑上所有 節(jié) 點 PA 之和為 4，在該路徑上發(fā)送 分組需要的能量之和為 3； 反向重路由 SNGF 鄰居表 信標交換 NFL 延遲估計 MAC 26 路徑 2：源節(jié)點 — C— B— A— 匯聚節(jié)點， 路徑上所有 節(jié) 點 PA 之和為 6，在 該路徑上發(fā)送分組需要的能量之和為 6； 路徑 3：源節(jié)點 —D—匯聚節(jié)點，路徑 上 所有節(jié)點 PA 之和為 3，在該路徑上 發(fā)送分組需要的能量之和為 4； 路徑 4：源節(jié)點 —F—E—匯聚節(jié)點，路徑上所有節(jié)點 PA 之和為 5，在該路徑上發(fā)送分組需要的能量之和為 6。 能量路 由 策略主要有以下幾種： (1)最大 PA 路由：從數(shù)據(jù)源到匯聚節(jié)點的所有路徑中選取節(jié)點 PA 之和最大的路徑。在 圖 33 中路徑 2 的 PA 之和最大，但路徑 2包含了路徑 1，因此 圖 33 能量路由算法示意圖 不是高效的從而被排除，選 擇 路徑 4。 (2)最小能量消耗 路由：從數(shù)據(jù)源到匯聚節(jié)點的所有路徑中選取節(jié)點耗能F(PA=4) E(PA=1) D(PA=3) 5a =2 4a =2 源節(jié)點 C(PA=2) 9a =2 B(PA=2) 2a =1 A(PA=2) 3a =2 10a =2 6a =2 7a =1 匯聚節(jié)點 1a =1 1a =1 8a =2 27 之和最少的路徑。在 圖 33 中選 擇 路徑 1。 (3)最少跳數(shù)路 由： 選取從數(shù)據(jù)源到匯聚節(jié)點跳數(shù)最 少的路徑。在圖 33中選 擇 路徑 3。 (4)最大最小 PA 節(jié)點路 由 ：每條路徑上有多個 節(jié) 點，是節(jié)點的可用能量不同，從中選取每條路徑中可用能 量 最小的節(jié)點來表示這條路徑的可用能量。如路徑 4 中 節(jié)點的可用能量最小為 1，所以該路徑的可用能量是 1。最大最小PA 節(jié)點路由策略就是選擇路徑可用能量最大的路徑。在 圖 33 中選擇路徑 3。 上述能量路 由 算 法 需要節(jié)點知道整個網(wǎng)絡的全局信息。由于傳 感器網(wǎng)絡存在資源約束，節(jié)點只能獲取局部信息， 因 此上述能量路 由 方法只是理想情況下的路 由 策略。 能量多路徑路由 傳統(tǒng)網(wǎng)絡的路 由 機制 往往 選擇源節(jié)點到目的節(jié)點之間跳數(shù)最小的路徑傳輸數(shù)據(jù)，但在無線傳感器網(wǎng)絡 中。如果頻繁使用同 — 條路徑傳輸數(shù)據(jù)，就會造成該路徑上節(jié) 點 因 能量消耗過快而過早失效，從而使整個 網(wǎng) 絡分割成互 不 相連的孤立部分．減少了整個網(wǎng)絡的生存期。為此， Rahul 等人提出了 — 種能量多路徑路 由 機制。該機制在源節(jié)點和 目 的節(jié)點之間建立多條路徑，根據(jù)路徑上節(jié)點的通信能 量 消耗以及節(jié)點的剩余能量情況 、給每條路徑賦 予 一定的選擇概率，使得數(shù)據(jù)傳輸均衡消耗整個網(wǎng)絡的能量，延長整個 網(wǎng) 絡的生存期。 能量多路徑路 由 協(xié)議包括路徑建 立 、數(shù)據(jù)傳播和路 由 維護三個過程。路徑建立過程是該協(xié)議的重點內(nèi)容。每個節(jié)點需要知道到達 目 的 節(jié) 點的所有下一跳節(jié)點，并 計 算選擇每個下一跳節(jié)點傳輸數(shù)據(jù)的概率。概率的選擇是根據(jù)節(jié)點到 28 目的節(jié)點的通信代價來 計 算的，在下面的描述 中用 )( iNCost 表 示 節(jié)點 i 到目的節(jié)點的通信代價。因為每個節(jié)點到達目的節(jié)點的路徑很多．所 以這個代價值是各個路徑的加權平均 值 。 由于作者的思想和處理辦 法是通過一本厚達幾百頁的書來向我們展示的，本人在拜讀了之后， 個人 認為 能量多路徑路 由 的 主 要過程 可以 簡潔的 描 述如下： (1)目 的節(jié)點 向 鄰居節(jié)點廣播路徑建立消息，啟動路徑建立過程。路徑建立消息中 包含一 個代價域，表示發(fā)出該消息的節(jié)點到 目 的節(jié)點路徑 上 的能量信息， 初 始值設置為零。 (2)當 節(jié)點收到鄰居節(jié)點發(fā)送的路徑建立消息時，相對發(fā)送該消息的鄰居 節(jié) 點，只有當 自 己 距 源節(jié)點 更 近，而 且 距 目 的節(jié)點更 遠 的情況下，才需要轉(zhuǎn)發(fā) 該消息．否則將丟棄該消息。 (3)如果節(jié)點決定轉(zhuǎn)發(fā)路徑建立消息，需要計算新的代價值來替換原來的 代價值 。當路徑建立消息從節(jié)點 iN 發(fā)送到 節(jié) 點 jN 時， 該路徑的通信代價值為節(jié)點 i 的代價值加 上兩個節(jié)點間的通信能量消耗。即： ),()(, ijiNN NNM e t r i cNC o s tCij ?? (31) 其中，ijNNC,表示 節(jié)點 jN 發(fā)送數(shù)據(jù)經(jīng) 由 節(jié)點 iN 路徑到達目的節(jié)點的代價，),( ij NNMetric 表 示節(jié)點 jN 到節(jié)點 iN 的通信能 量消耗，計算公式如下 ： ),( ij NNMetric ?? iijRe? (32) 這里 ?ije 表示節(jié)點 jN 和 iN 直接通信的能量消耗， ?iR 表示節(jié)點 iN 的剩余能量， 29 ? 、 ? 是常量，這個度量標 準 綜合考慮 了 節(jié)點的能量消耗以及節(jié)點的剩余能量。 (4)節(jié)點要放棄代價 太 大的路徑，節(jié)點 j 將節(jié)點 i 加入 本地路 由 表 jFT 中的條件是： ))}C(min(Ci{FTkjij N,NkN,Nj ??? (33) 其中 ? 為大于 1 的系統(tǒng)參數(shù)。 (5) 節(jié)點為路 由 表 中 每個 下一跳節(jié)點計算選擇概率。 節(jié)點選擇概率與能 量消耗成反比。節(jié)點 jN 使用如下公式計算選擇節(jié)點 iN 的概率： ???j kjijijFTk N,NN,NN,NC1C1P (34) (6)節(jié)點根據(jù)路 由表 中每項的能量代價和下一跳 節(jié) 點 選擇概率計算本身 到達 目的節(jié)點的代價 )N(Cost j 。 )N(Cost j 定義為經(jīng)由路 由 表中 節(jié) 點到達目的節(jié)點代價的平均 值 ，即： )N(Costjkjj ij N,NFTk N,N CP??? (35) 節(jié)點 jN 將用 )N(Cost j 值替 換消息中原有的代價值，然后向鄰居 節(jié) 點 廣 播該路由 建 立消 息。 在數(shù)據(jù) 傳播階段，對于接收的每個數(shù)據(jù)分組，節(jié)點根據(jù)概率從多個下 一 跳節(jié)點 中 選 擇一 個節(jié)點，并將數(shù)據(jù)分組轉(zhuǎn)發(fā)給該節(jié)點。路 由 的維護是通過 周 期性地從 目 的節(jié)點到源節(jié)點實施洪泛查詢來維持所有路徑的活動 性 。 Rahul 提出的能量多路徑路 由 綜合考慮了通信路徑上的消耗能量 30 和剩余能量，節(jié)點根據(jù)概率在路 由 表 中 選 擇 一個節(jié)點作為路 由 的下一跳節(jié)點 。由 于這個概率是 與 能 量 相關的，可以將通信能 耗分散到多條路徑上，從而可實現(xiàn)整個網(wǎng)絡的能量平穩(wěn)降級， 最大限度地延長網(wǎng)絡的生存期。 上面只是我個人從他的書里整理出來的一個簡潔的可行的能量多路徑路由 處理思路， 但對它的一些算法理解還有困難， 存在 誤解和 不足之處 ，懇請指正。 基于樹的能量有效路由協(xié)議 利用樹狀結構來處理問題是一種很多見的思路， 針對無線傳感器網(wǎng) 絡 的能量有效性問題，提出了基于樹的能量有效路由協(xié)議 (Treebased Energy Efficient Routing Protocol， TEERP)。 在 TEERP中，考慮節(jié)點的能量有效性，這主要從兩方面來 實現(xiàn)：① 選擇最少跳數(shù)的路徑。這對于功率不可調(diào)整的網(wǎng)絡，相當于選擇了最小能量路徑；②盡量讓剩余能量多的節(jié)點完成分組轉(zhuǎn)發(fā)功能，以提高 網(wǎng)絡的能量均衡性能。 首先，定義無線傳感器網(wǎng)絡目的節(jié)點只有一個 數(shù)據(jù)匯聚點 (Sink)節(jié)點， 樹的建立由 Sink節(jié)點開始。 Sink節(jié)點廣播 路由請求消息 (RREQ)， RREQ中攜帶廣播 ID、自己距離 Sink的跳數(shù)、 節(jié)點的能量 。節(jié)點在接收到第一個 RREQ時設置定時器，在定時器超時時 間 內(nèi)，比較新收到的 RREQ與當前緩存記錄，如果新的 RREQ距離 Sink的跳數(shù)小于當前的記錄，則根據(jù)新的 RREQ更新緩存中的記錄；如果跳數(shù)相等，則比較發(fā)送 RREQ節(jié)點的能量，如果能量大于當前緩存記錄的能量，則根據(jù)新的 RREQ更新緩存中的記錄 ，否則丟棄 RREQ。這樣，一直到全網(wǎng)所有的節(jié)點，建立全網(wǎng)的樹，如圖 34所示。 31 圖 34 樹結構 上述基于樹的能量路由協(xié)議已經(jīng)很大程度上提高了能量的利用率，同時延長了整個網(wǎng)絡的生存時間 。 但 為了保證節(jié)點之間的連通性，節(jié)點之間必須不斷地發(fā)送 Hello消息，這樣做的原因是：盡早發(fā)現(xiàn)失效節(jié)點，及時恢復 以更好地延長網(wǎng)絡的工作時間。 因此，這種處理方法中沒有引入休眠調(diào)度機制，而休眠是節(jié)省能量的最有效方式。 另外，傳感器網(wǎng)的覆蓋是需 要研究的另一個重要方面，如何在保證覆蓋的前提條件下，最優(yōu)地調(diào)度節(jié)點， 引入休眠機制， 并保證網(wǎng)絡的連通性以建立能量有效的路由是需要 不斷 研究的一個重要問題 。 一種新型集中式能量有效路由協(xié)議 本方法是 :首先讓基站利用 DTRAP(Dynamic Transmission Range Adjustment Protocol)來估計節(jié)點的位置。 在此對 DTRAP的主要思想作簡要的介紹 。 DTRAP的目的是得到兩個節(jié)點間的距離 ， 以期用最小的能量進行通信，從而節(jié)約能量。每個節(jié)點維護兩個表： MT(Message Table)和 NT(Neighborhood Table)。當節(jié)點 i收到 REQ包，就在 MT中添加一條，當 i準備回復時，就在 NT中把相應鄰居節(jié)點的通信狀態(tài)置為 REQ，對方回應后，對方會把自己 NT中鄰居節(jié)點的狀態(tài)置為確認 (ACK)， i 收到回應也把狀態(tài)置為 (ACK)，這 樣雙方就Sink 32 建立了通信。 NT中還存有與其余節(jié)點的通信距離。當一個節(jié)點 的鄰居節(jié)點個數(shù) N 小于下限 D 時，它就會增加它的發(fā)射功率，同時增時增大發(fā)射距離 Ti，以期得到更多的鄰居。 該 協(xié)議的工作過程如下：節(jié)點 i廣播一個 Req消息給所有的鄰居，當節(jié)點 j第一次收到 這個消息 (在 i的上一輪廣播中， 未收到這條消息，說明現(xiàn)在 i的發(fā)射范圍剛好能滿足 j 的接收信噪比，即這個發(fā)射能量是 i發(fā)向 j的最小 能量 )，而且它的鄰居節(jié)點個數(shù) jN 小于上限 HD ，它就把這條消息放在消息表 jMT 中，回復 jACK 給 i，并把鄰居表 jNT 中 i節(jié)點對應的狀態(tài)置為 REQ，i收到 jACK 后把鄰居表 iNT 中 j節(jié)點對應的狀態(tài)置為 REQ，再回復 iACK 給 j,j收到后把鄰居表 jNT 中 i節(jié)點對應的狀態(tài)置為 ACK，至此， i和 j點就能互相通信了。因為消息中帶有發(fā)射范圍，所以兩個節(jié)點都可以根據(jù)已經(jīng)確定的范圍選擇最小的發(fā)射能量。 本 能量 路由算法是以“輪 (round)”為工作時間單位，每一輪分為兩個階段：初始化階段和數(shù)據(jù)通信階段 。如圖 35所示。 (1)初始化階段 基站根據(jù) DTRAP發(fā)起廣播，確定每個節(jié)點與基站之間的距離，并確定每個節(jié)點的方位，從而大致估算出每個節(jié)點的位置。每個節(jié)點與基站的距離信息保存在節(jié)點中，當在以后節(jié)點作為多跳的簇首直接與基站通信時，利用這個距離信息調(diào)整發(fā)射功率，當然，基站也利用這個距離信息選擇不同的發(fā)射功率與不同的節(jié)點通信。然后每個節(jié)點把自己的能量情況發(fā)給基站，這樣基站就可以根據(jù)能量