傳感器網(wǎng)絡(luò)瓶頸節(jié)點(diǎn)識(shí)別算法及其實(shí)現(xiàn)
1.1萬(wàn)字 35頁(yè)
包含開題報(bào)告，任務(wù)書，論文，程序源碼



摘 要

無(wú)線傳感器網(wǎng)絡(luò)中的“瓶頸節(jié)點(diǎn)”是指那些由于隨機(jī)部署的原因而不得不成為連接兩個(gè)或多個(gè)區(qū)域的孤立的節(jié)點(diǎn)。由于這些節(jié)點(diǎn)處于特殊的位置，區(qū)域間傳送數(shù)據(jù)都必須經(jīng)過(guò)這些節(jié)點(diǎn)，以致其壽命大大小于其它的節(jié)點(diǎn)，一旦這些節(jié)點(diǎn)死亡，網(wǎng)絡(luò)將被割裂成不連通的分支，造成網(wǎng)絡(luò)不能正常工作，網(wǎng)絡(luò)壽命的終結(jié)，因此研究這類“瓶頸節(jié)點(diǎn)”有十分重要的意義。由于傳感器節(jié)點(diǎn)計(jì)算和存儲(chǔ)能力有限，“瓶頸節(jié)點(diǎn)”很難計(jì)算出來(lái)。于是[1]中提出一種新的概念“準(zhǔn)瓶頸節(jié)點(diǎn)”，并使用分布式算法尋找到這些節(jié)點(diǎn)。
經(jīng)過(guò)本文分析，這個(gè)尋找“準(zhǔn)瓶頸節(jié)點(diǎn)”算法并非是優(yōu)化的，算法執(zhí)行的結(jié)果包含相當(dāng)數(shù)量的非瓶頸節(jié)點(diǎn)，這類節(jié)點(diǎn)并不是連接兩個(gè)或多個(gè)區(qū)域的孤立節(jié)點(diǎn)。本文將分析這類非瓶頸節(jié)點(diǎn)的特點(diǎn)，并將其稱為“偽瓶頸節(jié)點(diǎn)”，在此基礎(chǔ)上，分析“準(zhǔn)瓶頸節(jié)點(diǎn)”算法的缺陷，隨后本文將根據(jù)這些特點(diǎn)提出“二跳準(zhǔn)瓶頸節(jié)點(diǎn)”定義，新的定義將消除“偽瓶頸節(jié)點(diǎn)”的影響。然后根據(jù)新定義提出與之相對(duì)應(yīng)的算法用于尋找這些“二跳準(zhǔn)瓶頸節(jié)點(diǎn)”，并且證明該算法在時(shí)間復(fù)雜度不超過(guò) 的情況下找到的節(jié)點(diǎn)更加關(guān)鍵和優(yōu)化。本次畢業(yè)設(shè)計(jì)還將實(shí)現(xiàn)一個(gè)簡(jiǎn)單的模擬器，用于對(duì)兩種算法的性能做比較，并測(cè)量能量消耗速度，最后得出結(jié)論：在無(wú)線傳感器網(wǎng)絡(luò)中二跳準(zhǔn)瓶頸節(jié)點(diǎn)具有最快的能量消耗速度。

關(guān)鍵詞：無(wú)限傳感網(wǎng)絡(luò)；網(wǎng)絡(luò)壽命；瓶頸節(jié)點(diǎn)；準(zhǔn)瓶頸節(jié)點(diǎn)；二跳準(zhǔn)瓶頸節(jié)點(diǎn)





A New Approach to the Bottleneck Problem in Wireless Sensor Network
Abstract
“Bottleneck Nodes” are those connect two or more areas alone with the reason of the deployment．Due to those particular positions, the data transferred between areas will surely go through those nodes. And then the lifetime of those nodes will obviously less than other nodes. Once those nodes are dead, the network would be divided to several unconnected parts and it means the network can not support the application any more. It is really a challenge to find out those nodes with sensor’s limited capability of calculation. [1] presents a new concept “quasi—Bottleneck Nodes” , and a distributed algorithm to find out all the “quasi—Bottleneck Nodes”.
In this paper, we will prove that “quasi—Bottleneck Nodes” arithmetic is not optimal, and then we will base the concept described in [1], and present a new concept “two-Hop quasi Bottleneck Nodes”, also we will give the new algorithm and prove that its cost is in .Besides that we will realize a simple simulator for experiment in this paper. The simulator aims at simulating both algorithms and holding a contrast between both algorithms.

Key Words：Wireless sensor network; lifetime; bottleneck; quasi—Bottleneck Nodes; two-Hop quasi Bottleneck Nodes






目 錄
1 緒論 1
1.1 課題背景及目的 1
1.2 國(guó)內(nèi)外研究狀況 1
1.3 課題研究方法 2
1.4 論文構(gòu)成及研究?jī)?nèi)容 2
2 瓶頸節(jié)點(diǎn) 3
2.1 瓶頸節(jié)點(diǎn)概述 3
2.2 概念定義 3
2.2.1定義信宿 3
2.2.2定義多跳 3
2.2.3定義網(wǎng)絡(luò)壽命 4
2.2.4定義瓶頸節(jié)點(diǎn) 4
2.3 準(zhǔn)瓶頸節(jié)點(diǎn)概念 5
2.4 準(zhǔn)瓶頸節(jié)點(diǎn)算法 6
3 二跳準(zhǔn)瓶頸節(jié)點(diǎn)概念和算法 8
3.1 準(zhǔn)瓶頸節(jié)點(diǎn)算法的缺陷分析 8
3.2 二跳準(zhǔn)瓶頸節(jié)點(diǎn)的概念 9
3.3 二跳準(zhǔn)瓶頸算法的提出 10
3.4 二跳準(zhǔn)瓶頸節(jié)點(diǎn)的時(shí)間復(fù)雜度分析 11
4 算法性能比較 13
4.1 模擬環(huán)境介紹 13
4.2 改進(jìn)后算法性能對(duì)比 15
4.3 能量消耗速度對(duì)比 17
5 結(jié)論 18
致謝 18
參考文獻(xiàn) 18
附錄 18
附錄A 一跳準(zhǔn)節(jié)點(diǎn)算法實(shí)現(xiàn) 18
附錄B 二跳準(zhǔn)瓶頸節(jié)點(diǎn)算法的實(shí)現(xiàn) 18
附錄C TopDisc三色算法實(shí)現(xiàn) 18



參考文獻(xiàn)
[1] 田樂,謝東亮,韓冰,張雷.無(wú)線傳感器網(wǎng)絡(luò)中瓶頸節(jié)點(diǎn)的研究[J].Journal of Software軟件學(xué)報(bào)
[2] Holger Karl, Andress Willing, 邱天爽等譯.無(wú)線傳感器網(wǎng)絡(luò)協(xié)議與體系結(jié)構(gòu)[M].北京:電子工業(yè)出版社
[3] DAVID R.KARGER, CLIFFORD STEIN. A New Approach to the Minimum Cut Problem [J].Journal of the ACM (JACM), Volume 43, Issue 4 , July