本文選題：無(wú)線網(wǎng)絡(luò) + 支配集�。� 參考：《曲阜師范大學(xué)》2017年碩士論文

【摘要】：隨著無(wú)線技術(shù)的不斷進(jìn)步,無(wú)線網(wǎng)絡(luò)可以廣泛地應(yīng)用于各種領(lǐng)域,如軍事,醫(yī)療,環(huán)境等。然而,無(wú)線網(wǎng)絡(luò)的缺點(diǎn)限制了網(wǎng)絡(luò)的性能,造成能量浪費(fèi)、信息冗余等。解決這些問(wèn)題的高效的技術(shù)是拓?fù)淇刂�。連通支配集是無(wú)線網(wǎng)絡(luò)中拓?fù)淇刂频拇硇约夹g(shù),它方便了許多工作的實(shí)現(xiàn),如廣播,路由,數(shù)據(jù)采集等。本文通過(guò)對(duì)現(xiàn)有連通支配集的分析與研究,在SINR(Signal-to-Interference-plus-Noise-Ratio)模型下研究了CDS的構(gòu)造算法。近年來(lái),大多數(shù)的工作使用簡(jiǎn)單的基于圖或者基于距離的干擾模型,來(lái)研究CDS構(gòu)造問(wèn)題。對(duì)此,很少有文章的研究模型為物理干擾模型(SINR模型)。SINR模型是一個(gè)考慮到累積干擾的模型,且接近現(xiàn)實(shí)的自然環(huán)境。本文共分為五章。第1章說(shuō)明了本文研究的背景以及現(xiàn)狀。第2章對(duì)現(xiàn)存的連通支配集工作進(jìn)行了總結(jié),并分析了其中經(jīng)典的構(gòu)造算法。第3章給出了SINR模型下構(gòu)建自穩(wěn)定的連通支配集算法(DS_CDS-1),該算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)劃分在不同的網(wǎng)格中,它包括兩個(gè)階段,第一階段形成MIS,第二階段,MIS中的節(jié)點(diǎn)通過(guò)尋找相鄰方格中的鄰居節(jié)點(diǎn),連通得到CDS,最后證明該CDS可以得到常數(shù)性能的近似因子且是自穩(wěn)定的。第3章的算法并沒(méi)有考慮連通支配集的優(yōu)化因子,為了近一步地解決構(gòu)建SINR模型中的連通支配集問(wèn)題,第4章給出了SINR模型下自穩(wěn)定且限制直徑的連通支配集構(gòu)造算法(DS_CDS-2),該算法和第3章中的算法相比,縮小了CDS可得到的常數(shù)性能的近似因子,并減小了時(shí)間復(fù)雜度,且可以證明CDS的直徑所滿足的上界。第4章分析SINR約束時(shí),做了相應(yīng)的假設(shè)簡(jiǎn)化SINR模型,以便于分析與計(jì)算。為了進(jìn)一步地優(yōu)化算法的真實(shí)性,在第5章中我們?cè)僖淮卧O(shè)計(jì)了SINR模型中自穩(wěn)定的分布式CDS構(gòu)造算法(DS_CDS-3),我們繼續(xù)關(guān)注CDS的兩個(gè)重要的性能指標(biāo),密度以及CDS的直徑,并取得了相應(yīng)的研究成果。據(jù)我們所知,這是實(shí)際SINR模型下,對(duì)于分布式CDS構(gòu)造算法的密度和直徑漸近地最優(yōu)的自穩(wěn)定結(jié)果。第6章總結(jié)了全文,并展望了未來(lái)的進(jìn)一步研究。
[Abstract]:With the development of wireless technology, wireless network can be widely used in various fields, such as military, medical, environment and so on. However, the shortcomings of wireless networks limit the network performance, resulting in energy waste, information redundancy and so on. The efficient technique to solve these problems is topology control. Connected dominating set is the representative technology of topology control in wireless network. It facilitates the implementation of many work, such as broadcast, routing, data acquisition and so on. Based on the analysis and study of the existing connected dominating sets, the construction algorithm of CDS is studied under the SINR (Signal-to-Interference-plus-Noise-Ratio) model. In recent years, most of the work uses simple graph-based or distance-based interference models to study the construction of CDS. For this reason, few research models are physical interference model (SINR model). SINR model is a model which takes into account cumulative disturbance and is close to the real environment. This paper is divided into five chapters. Chapter 1 explains the background and present situation of this paper. In chapter 2, the existing work of connected dominating set is summarized, and the classical construction algorithm is analyzed. In chapter 3, the algorithm of constructing a self-stable connected dominating set (DSSP CDS-1) under the SINR model is presented. The algorithm divides the nodes in the network into different meshes, and it includes two stages. In the first stage, MISS is formed, and in the second stage, the nodes in MIS are connected to obtain the CDS by finding the neighbor nodes in the adjacent squares. Finally, it is proved that the CDS can obtain the approximate factor of constant performance and is self-stable. In chapter 3, the algorithm does not consider the optimization factor of the connected dominating set. In order to solve the problem of constructing the connected dominating set in the SINR model, In chapter 4, we present a self-stable and diameter-limiting connected dominating set construction algorithm (DSSCS-2) in the SINR model. Compared with the algorithm in Chapter 3, this algorithm reduces the approximate factor of the constant performance of the CDS and reduces the time complexity. The upper bound of the diameter of CDS can be proved. In chapter 4, when analyzing the SINR constraint, the corresponding assumptions are made to simplify the SINR model for easy analysis and calculation. In order to further optimize the authenticity of the algorithm, in Chapter 5, we once again design a self-stable distributed CDS construction algorithm (DSSCS-3) in the SINR model. We continue to pay attention to the two important performance indicators of CDS, density and diameter of CDS. And obtained the corresponding research result. As far as we know, this is the asymptotically optimal self-stability result for the density and diameter of the distributed CDS construction algorithm under the actual SINR model. Chapter 6 summarizes the full text and looks forward to further research in the future.
【學(xué)位授予單位】：曲阜師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：TN92

【相似文獻(xiàn)】

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

1 孫立山;郝燕玲;;能量限制的連通支配集分布式構(gòu)造[J];計(jì)算機(jī)工程與應(yīng)用;2006年32期

2 馬婭婕;田翔川;;網(wǎng)絡(luò)拓?fù)渚酆系膸捈訖?quán)支配集算法研究[J];小型微型計(jì)算機(jī)系統(tǒng);2007年04期

3 張e，

本文編號(hào)：2083543