【摘要】：近年來,隨著無線通信技術(shù)與設(shè)備的發(fā)展,無線網(wǎng)絡(luò)在各種領(lǐng)域得到了廣泛應(yīng)用。無線設(shè)備使用局部廣播的方式進(jìn)行彼此之間的通信造成了網(wǎng)絡(luò)中大量信息的冗余與能量的浪費(fèi)。如何減少網(wǎng)絡(luò)中信息的冗余、節(jié)約能量是無線網(wǎng)絡(luò)協(xié)議設(shè)計(jì)過程必需要考慮的問題。從某種意義上來說這一問題決定了無線網(wǎng)絡(luò)的服務(wù)質(zhì)量,而拓?fù)淇刂颇軌蚪鉀Q上述問題,因此設(shè)計(jì)有效的拓?fù)淇刂茀f(xié)議是十分必要的。所謂拓?fù)淇刂?是指在無線網(wǎng)絡(luò)相應(yīng)的圖模型中構(gòu)造具有某些特殊性質(zhì)(如,連通性、稀疏性、低干擾等)的子圖�？刂萍峭�?fù)淇刂浦械囊环N重要的方法,在無線網(wǎng)絡(luò)中得到了廣泛研究。本文通過對現(xiàn)有控制集算法的研究與分析,首先在beep模型下提出了BMDS. BCDS與BCDSC算法。離散beep模型是一個極其嚴(yán)格的局部廣播模型,該模型僅依賴載波偵聽,網(wǎng)絡(luò)中的節(jié)點(diǎn)不需要任何先驗(yàn)信息,例如節(jié)點(diǎn)的唯一標(biāo)識符,網(wǎng)絡(luò)的拓?fù)湫畔⒌取Ｈ缓?在SINR模型下設(shè)計(jì)了DSSMIS與DSS_CDS算法。SINR(Signal-to-Interference-plus-Noise-Ratio)模型是一個更加切合實(shí)際的累積干擾模型。事實(shí)上,我們還通過理論分析分別證明了它們的有效性與正確性。本文共分為五章。第1章介紹了研究的背景、意義與研究現(xiàn)狀。第2章對當(dāng)前存在的一些控制集算法進(jìn)行了分類與總結(jié),并對某些經(jīng)典的控制集構(gòu)造協(xié)議進(jìn)行了分析。第3章首先給出了離散beep模型下的一個分布式最小控制集的近似算法(Beeping a Minimum Dominating Set, BMDS),該算法是一個基于局部控制度(節(jié)點(diǎn)的非受控鄰接點(diǎn)的數(shù)目)的貪心選擇策略,然后設(shè)計(jì)了beep模型下的極大獨(dú)立集構(gòu)造算法以及弱連通控制集構(gòu)造算法,基于上述兩種算法,提出了beep模型下的連通控制集構(gòu)造算法(Beeping a Connected Dominating Set, BCDS)。最后利用節(jié)點(diǎn)間的沖突提出了另一個連通控制集的構(gòu)造算法(Beeping a Connected Dominating Set with Collision, BCDSC)。在一個自穩(wěn)定的系統(tǒng)是指具有錯誤容忍能力的系統(tǒng),即能夠承受發(fā)生的錯誤,并且在沒有外力干擾的情況下從這些短暫的錯誤中恢復(fù)過來。由于無線網(wǎng)絡(luò)面臨著復(fù)雜的工作環(huán)境,其拓?fù)渥兓瘯r(shí)常發(fā)生變化,所以自穩(wěn)定性是無線網(wǎng)絡(luò)協(xié)議設(shè)計(jì)過程中必要選擇。為了保證這些自穩(wěn)定算法能夠在實(shí)際網(wǎng)絡(luò)中應(yīng)用,還必須在協(xié)議的設(shè)計(jì)過程中考慮干擾因素。第4章解決了自穩(wěn)定性與干擾的問題,基于分區(qū)與著色的思想,首先在SINR模型下提出了分布式自穩(wěn)定的極大獨(dú)立集構(gòu)造算法(Distributed Self-Stabilizing Maximal Independent Set construction algorithm, DSS_MIS),然后在概算法的基礎(chǔ)上進(jìn)行改進(jìn)最終得到了分布式自穩(wěn)定的連通控制集構(gòu)造算法(Distributed Self-Stabilizing Connected Dominating Set construction algorithm, DSS CDS)。第5章對本文進(jìn)行了總結(jié),并對未來進(jìn)一步的研究工作進(jìn)行了展望。
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2015
【分類號】：TN92

【相似文獻(xiàn)】

相關(guān)期刊論文 前10條

1 強(qiáng)宇,劉宗田,林煒,時(shí)百勝,李云;一種模糊概念格構(gòu)造算法研究[J];計(jì)算機(jī)工程與應(yīng)用;2004年29期

2 樊建席;最小T－2倍樹的構(gòu)造算法[J];青島大學(xué)學(xué)報(bào)(自然科學(xué)版);1996年04期

3 楊凱;馬垣;張小平;;基于屬性的概念格快速漸進(jìn)式構(gòu)造算法[J];計(jì)算機(jī)應(yīng)用與軟件;2006年12期

4 楊海峰;張繼福;;粗糙概念格及構(gòu)造算法[J];計(jì)算機(jī)工程與應(yīng)用;2007年24期

5 余遠(yuǎn);錢旭;鐘鋒;李曉瑞;;基于最大概念的概念格增量構(gòu)造算法[J];計(jì)算機(jī)工程;2009年21期

6 趙煥平;;圈圖的點(diǎn)可區(qū)別強(qiáng)全染色算法[J];計(jì)算機(jī)與現(xiàn)代化;2013年09期

7 董輝;馬垣;宮璽;;概念格并行構(gòu)造算法研究[J];廣西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

8 鄭金英;滕春霞;;概念格構(gòu)造算法的現(xiàn)狀與發(fā)展前景[J];硅谷;2011年22期

9 林春杰;普杰信;張瑞玲;;近似概念格及其增量構(gòu)造算法研究[J];計(jì)算機(jī)應(yīng)用研究;2012年01期

10 杜秋香;張繼福;張素蘭;;概念特化的概念格更新構(gòu)造算法[J];智能系統(tǒng)學(xué)報(bào);2008年05期

相關(guān)會議論文 前5條

1 曲立平;劉大昕;楊靜;張萬松;;基于屬性的概念格快速漸進(jìn)式構(gòu)造算法[A];第二十四屆中國數(shù)據(jù)庫學(xué)術(shù)會議論文集（研究報(bào)告篇）[C];2007年

2 楊本良;;壓縮候選的貝葉斯信念網(wǎng)絡(luò)構(gòu)造算法[A];廣西計(jì)算機(jī)學(xué)會2005年學(xué)術(shù)年會論文集[C];2005年

3 申錦標(biāo);;一種新穎的概念格構(gòu)造算法[A];全國第20屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集（上冊）[C];2009年

4 高茜;周大均;李愛民;;Petri網(wǎng)改進(jìn)的可覆蓋性樹的構(gòu)造算法[A];全國第20屆計(jì)算機(jī)技術(shù)與應(yīng)用學(xué)術(shù)會議（CACIS·2009）暨全國第1屆安全關(guān)鍵技術(shù)與應(yīng)用學(xué)術(shù)會議論文集（上冊）[C];2009年

5 韓鋒;張鴻賓;;不連通模型上多尺度Reeb圖的構(gòu)造算法[A];2008'中國信息技術(shù)與應(yīng)用學(xué)術(shù)論壇論文集（二）[C];2008年

相關(guān)碩士學(xué)位論文 前10條

1 張海燕;準(zhǔn)循環(huán)LDPC碼的構(gòu)造算法研究[D];西安電子科技大學(xué);2014年

2 李曉龍;基于最大閉合項(xiàng)集的概念構(gòu)造及應(yīng)用[D];燕山大學(xué);2016年

3 姜琴;基于多屬性消減的概念格構(gòu)造算法研究[D];鄭州大學(xué);2016年

4 朱文君;構(gòu)造概念格的權(quán)值優(yōu)化改進(jìn)算法研究[D];上海海洋大學(xué);2016年

5 賈莉俐;無線網(wǎng)絡(luò)中控制集構(gòu)造算法的研究[D];曲阜師范大學(xué);2015年

6 孫斌斌;概念三元格構(gòu)造算法研究[D];西安電子科技大學(xué);2015年

7 王紹斐;概念格構(gòu)造算法的研究及其在本體中的應(yīng)用[D];大連交通大學(xué);2010年

8 劉曉今;概念三元格構(gòu)造算法及應(yīng)用研究[D];西安電子科技大學(xué);2013年

9 吳新榮;全可逆遞進(jìn)網(wǎng)格構(gòu)造算法研究[D];中南大學(xué);2007年

10 黃永城;基于多核環(huán)境的基因貝葉斯網(wǎng)絡(luò)構(gòu)造算法研究與實(shí)現(xiàn)[D];上海交通大學(xué);2012年

，

本文編號：2565810