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

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

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

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

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