本文關(guān)鍵詞：無線傳感器網(wǎng)絡(luò)中分布式廣播算法研究

  更多相關(guān)文章： 全局廣播 SINR 分布式 異步無線網(wǎng) 確定性算法

【摘要】：廣播是無線傳感器網(wǎng)絡(luò)中的基本問題之一,它的效率直接決定了許多高層應(yīng)用和協(xié)議(如路由發(fā)現(xiàn)協(xié)議)的性能。根據(jù)所要廣播的消息個數(shù)不同,可以將廣播問題劃分為單消息廣播和多消息廣播。在無線傳感器網(wǎng)絡(luò)中,無線通信往往受到干擾的影響,因此干擾建模對設(shè)計高效的網(wǎng)絡(luò)協(xié)議是非常重要的。近年來,物理干擾模型得到了廣泛應(yīng)用。在物理干擾模型中,干擾隨著距離的增加而減小并具有全局累加性特征,符合無線傳感器網(wǎng)絡(luò)的實際情況�，F(xiàn)實中的無線傳感器網(wǎng)絡(luò)往往是一個分布式系統(tǒng),因而設(shè)計高效的分布式廣播算法更加具有現(xiàn)實意義。以往同步通訊模型下的分布式確定性單消息廣播算法為了從邏輯上將整個網(wǎng)絡(luò)進行網(wǎng)格劃分,需要每個節(jié)點知道自己的坐標(biāo)信息。這將產(chǎn)生如下兩個問題,第一,算法執(zhí)行的正確性和精確性在很大程度上取決于網(wǎng)絡(luò)中節(jié)點位置的定位精度;第二,為部分或全部節(jié)點配備GPS(Global Position System)設(shè)備將會帶來高成本和高能耗。此外,以往異步通訊模型下的分布式多消息廣播算法采用的是基于圖的干擾模型而不是更加符合實際的物理干擾模型。鑒于以上原因,本文研究基于物理干擾模型的無坐標(biāo)依賴的分布式廣播算法的設(shè)計,主要內(nèi)容如下。(1)在同步通訊模型下,設(shè)計了兩個基于標(biāo)準(zhǔn)物理干擾模型的分布式確定性單消息廣播算法。第一個廣播算法(the Time Efficient Global Broadcast,TEGB)首先從每一層節(jié)點中選取一個極大獨立集,接著將該極大獨立集劃分為若干子集以實現(xiàn)廣播消息最大程度的并發(fā)傳輸。理論分析表明,TEGB的時間復(fù)雜度為O(Dlogn),這里n表示節(jié)點總數(shù),D為網(wǎng)絡(luò)的直徑。與Jurdzinski等人所提出的算法DetGenBroadcast相比,TEGB在時間性能上改進了一個對數(shù)因子。為了減少廣播消息的冗余傳播,提出了第二個廣播算法(the Tree-Based Global Broadcast,TBGB)。算法TBGB可以構(gòu)造網(wǎng)絡(luò)的單向生成樹,在該生成樹中,只有非葉子節(jié)點需要轉(zhuǎn)發(fā)廣播消息。與TEGB相比,TBGB可以大大降低廣播消息的冗余傳播。理論分析表明,TBGB的時間復(fù)雜度為O(DΔlogn),這里Δ為最大節(jié)點度。仿真結(jié)果驗證了以上的理論分析。(2)在異步通訊模型下,設(shè)計了基于擴展物理干擾模型的分布式多消息廣播算法(the Distributed Asynchronous Multiple-message Broadcast,DAMB)�；谝粋�預(yù)先定義的傳輸骨干結(jié)構(gòu),算法DAMB可以在OckDn-+?+))]1(2([logτ時間內(nèi)解決多消息廣播問題,這里D表示網(wǎng)絡(luò)中匯聚(sink)節(jié)點的離心率,k表示廣播消息的個數(shù),τ表示消息在信道中的傳播時延,c是一個常數(shù)。當(dāng)k=n時,算法DAMB的容量下界為??))8/1((Wc,這里W表示無線信道的帶寬。注意,DAMB是擴展物理干擾模型下第一個分布式異步多消息廣播算法。
【關(guān)鍵詞】：全局廣播 SINR 分布式 異步無線網(wǎng) 確定性算法
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP212.9;TN929.5
【目錄】：

• 摘要3-4
• Abstract4-8
• 第1章 緒論8-13
• 1.1 研究背景及意義8-9
• 1.2 國內(nèi)外研究現(xiàn)狀9-11
• 1.2.1 基于圖的干擾模型下廣播問題的研究進展9-10
• 1.2.2 物理干擾模型下廣播問題的研究進展10-11
• 1.2.3 異步通訊模型下廣播問題的研究進展11
• 1.3 論文組織結(jié)構(gòu)11-13
• 第2章 廣播算法設(shè)計概述13-18
• 2.1 無線傳感器網(wǎng)絡(luò)建模13-14
• 2.2 廣播算法模型14-15
• 2.2.1 干擾模型14-15
• 2.2.2 功率分配模型15
• 2.3 局部廣播問題與全局廣播問題15
• 2.4 廣播算法分類15-17
• 2.4.1 同步廣播算法和異步廣播算法15-16
• 2.4.2 集中式廣播算法和分布式廣播算法16
• 2.4.3 隨機廣播算法和確定性廣播算法16-17
• 2.5 本章小結(jié)17-18
• 第3章 SINR模型下的分布式確定性單消息廣播算法研究18-41
• 3.1 網(wǎng)絡(luò)模型和定義18-19
• 3.2 極大獨立集子協(xié)議MMIS19-22
• 3.2.1 MMIS執(zhí)行環(huán)境的建立20
• 3.2.2 MMIS的構(gòu)造和性能分析20-22
• 3.3 時間高效的分布式確定性單消息廣播算法TEGB22-31
• 3.3.1 廣播圖和層次劃分22-24
• 3.3.2 TEGB算法設(shè)計24-26
• 3.3.3 TEGB算法性能分析及正確性證明26-31
• 3.4 基于樹的分布式確定性單消息廣播算法TBGB31-35
• 3.4.1 TBGB算法設(shè)計31-33
• 3.4.2 TBGB算法性能分析及正確性證明33-35
• 3.5 仿真設(shè)計35-39
• 3.5.1 仿真環(huán)境搭建35-36
• 3.5.2 仿真結(jié)果與分析36-39
• 3.6 本章小結(jié)39-41
• 第4章 擴展物理干擾模型下分布式異步多消息廣播算法研究41-48
• 4.1 網(wǎng)絡(luò)模型及相關(guān)定義41-42
• 4.2 骨干結(jié)構(gòu)構(gòu)造42-43
• 4.3 DAMB算法設(shè)計43-47
• 4.3.1 傳輸子協(xié)議44-45
• 4.3.2 DAMB理論分析45-47
• 4.4 本章小結(jié)47-48
• 第5章 總結(jié)與展望48-50
• 參考文獻50-54
• 在讀期間發(fā)表的學(xué)術(shù)論文及研究成果54-55
• 致謝55

【相似文獻】

中國期刊全文數(shù)據(jù)庫 前10條

1 韓秀苓，，程凡，高建林，李傳光;管道自適應(yīng)有源噪聲控制算法[J];Journal of Beijing Institute of Technology(English Edition);1995年01期

2 陶新民;徐晶;童智靖;劉玉;;不均衡數(shù)據(jù)下基于陰性免疫的過抽樣新算法[J];控制與決策;2010年06期

3 趙國峰;閆亮;;用于快速流分類的關(guān)鍵字分解Hash算法[J];計算機工程;2010年16期

4 郭雷勇;譚洪舟;高守平;郭笑梅;;RFID系統(tǒng)閱讀器反碰撞算法分類與研究[J];計算機技術(shù)與發(fā)展;2009年09期

5 郝水俠,李凡長;多Agent的并行思智算法[J];計算機工程與應(yīng)用;2004年10期

6 劉貝家;方景龍;;基于SVDD的多示例學(xué)習(xí)算法[J];科技通報;2011年02期

7 田大東;鄧偉;;基于不同懲罰系數(shù)的SMO改進算法[J];計算機應(yīng)用;2008年09期

8 許敏;王士同;顧鑫;;TL-SVM:一種遷移學(xué)習(xí)算法[J];控制與決策;2014年01期

9 李雅林;張化祥;張順;;基于近鄰加權(quán)及多示例的多標(biāo)記學(xué)習(xí)改進算法[J];計算機工程與應(yīng)用;2013年16期

10 羅玉華,李三立;RISC多發(fā)射結(jié)構(gòu)中循環(huán)優(yōu)化的軟件流水算法[J];計算機學(xué)報;1993年09期

中國博士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 吳濤;粒子群及量子行為粒子群優(yōu)化算法的改進研究[D];西南交通大學(xué);2014年

2 徐勇;分布式壓縮感知的算法及其應(yīng)用研究[D];中國地質(zhì)大學(xué);2015年

3 蔡先發(fā);基于圖的半監(jiān)督算法及其應(yīng)用研究[D];華南理工大學(xué);2013年

4 蔣良孝;樸素貝葉斯分類器及其改進算法研究[D];中國地質(zhì)大學(xué);2009年

5 李美安;普適分布式互斥算法及應(yīng)用[D];電子科技大學(xué);2007年

6 孫巖;貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)算法研究與應(yīng)用[D];大連理工大學(xué);2010年

7 吳偉寧;主動學(xué)習(xí)算法中采樣策略研究[D];哈爾濱工業(yè)大學(xué);2013年

8 汪慶淼;基于目標(biāo)函數(shù)的模糊聚類新算法及其應(yīng)用研究[D];江蘇大學(xué);2014年

9 戴朝華;搜尋者優(yōu)化算法及其應(yīng)用研究[D];西南交通大學(xué);2009年

10 李小冬;核極限學(xué)習(xí)機的理論與算法及其在圖像處理中的應(yīng)用[D];浙江大學(xué);2014年

中國碩士學(xué)位論文全文數(shù)據(jù)庫 前10條

1 李超;基于標(biāo)簽傳播及適合度的社團聚類算法研究[D];西南大學(xué);2015年

2 劉晨曦;RFID定位VIRE算法的研究與改進[D];貴州師范大學(xué);2015年

3 馬睿;利用巖石光譜和改進的PC算法實現(xiàn)礦物的識別[D];新疆大學(xué);2015年

4 萬猛;推薦系統(tǒng)攻擊檢測算法的研究[D];電子科技大學(xué);2014年

5 劉排;基于OMNeT++的無線傳感器網(wǎng)絡(luò)節(jié)點定位改進算法的研究[D];河北工業(yè)大學(xué);2015年

6 陳辰;無線通信領(lǐng)域MIMO檢測類算法的硬件加速技術(shù)研究[D];國防科學(xué)技術(shù)大學(xué);2013年

7 韓超;場景分類與道路場景異常識別算法研究[D];北京交通大學(xué);2016年

8 董楠;行車熱點中無監(jiān)督聚類算法的研究與應(yīng)用[D];東北大學(xué);2014年

9 林玉琪;基于多智能體的數(shù)據(jù)流聚類算法研究[D];福州大學(xué);2013年

10 曹鵬;基于Spark平臺的聚類算法的優(yōu)化與實現(xiàn)[D];北京交通大學(xué);2016年

本文編號：1046579