圖論在計算機和無線傳感器網(wǎng)絡中的應用.pdf

1、計算機的誕生徹底改變了人類的計算歷史，它以強大，高速，精確計算能力，深入現(xiàn)代生活、生產(chǎn)以及科研的各個領(lǐng)域，扮演著非常重要的角色，可以說計算機的發(fā)展正在推動著整個社會的進步。
　　 本論文使用圖論基礎(chǔ)理論和建模方法對現(xiàn)代計算機三個主流體系結(jié)構(gòu)，分別是并行計算機，無線傳感器網(wǎng)絡以及網(wǎng)絡計算的相關(guān)熱點問題進行探討。本論文總共包括五章，三個主題，其中第二章和第三章是圍繞以網(wǎng)格網(wǎng)絡作為拓撲結(jié)構(gòu)的并行計算機節(jié)點間容錯適應性路由這個主題展開的

2、，第四章討論無線傳感器網(wǎng)絡中跟蹤移動物體產(chǎn)生數(shù)據(jù)的多基站實時路由問題，第五章提出了一個基于網(wǎng)格技術(shù)的數(shù)學網(wǎng)絡計算模型。前兩個主題是2007年到2009年在法國巴黎第十一大學完成的內(nèi)容，第三個是2005年到2007年在蘭州大學完成的。
　　 論文的第二、三章主要研究網(wǎng)格網(wǎng)絡中容錯自適應路由問題，在該問題上結(jié)合傳統(tǒng)模型提出了一個新的模型，及其相應的路由算法。通過在傳統(tǒng)的容錯塊內(nèi)部構(gòu)建生成樹，消息數(shù)據(jù)包可以通過這些內(nèi)部的生成樹被路由到

3、容錯塊內(nèi)部，這樣就保證了只要節(jié)點與網(wǎng)絡是保持連通的，那么消息一定可以送達到該節(jié)點，保證了網(wǎng)絡中節(jié)點的最大化利用。容錯塊的構(gòu)建方法簡單容易實現(xiàn)，并且構(gòu)建過程完全是自主的，可以根據(jù)網(wǎng)絡的實時狀態(tài)調(diào)整容錯塊的規(guī)模，當容錯塊中的節(jié)點恢復正常，不需要停機重啟機器，容錯塊可以自行消失，顯著提高了并行計算機的整體性能。
　　 第四章介紹了一種無線傳感器網(wǎng)絡的新應用，即無線傳感器網(wǎng)絡中跟蹤移動物體時產(chǎn)生數(shù)據(jù)的多基站實時路由問題，該問題在文章中被

4、證明是NP完全的，并且提出三種啟發(fā)式算法來解決不同的應用需求，最短路徑路由主要用來滿足路由的延遲限制，最大利用率路由用來滿足網(wǎng)絡節(jié)能的要求，而最后一種激活優(yōu)先路由權(quán)衡考慮延遲限制和網(wǎng)絡節(jié)能，通過模擬實驗和理論分析得出，其中激活優(yōu)先算法不僅可以滿足延遲限制而且能夠獲得較好的節(jié)能效果?？梢赃m用于無線傳感器網(wǎng)絡中對跟蹤移動物體所產(chǎn)生數(shù)據(jù)進行多基站路由。
　　 最后一章介紹了一種基于網(wǎng)格技術(shù)的數(shù)學網(wǎng)絡計算環(huán)境，通過該環(huán)境可以集成地域上分