發(fā)布時間：2018-06-11 10:26

  本文選題：Ad + Hoc傳感器網(wǎng)絡(luò)　； 參考：《天津工業(yè)大學(xué)》2016年碩士論文

【摘要】：Ad Hoc傳感器網(wǎng)絡(luò)是一種具有大規(guī)模性、自組織性、無基礎(chǔ)設(shè)施支持等特點(diǎn)的網(wǎng)絡(luò),能夠應(yīng)用于各個領(lǐng)域,具有重要的現(xiàn)實(shí)意義。該網(wǎng)絡(luò)利用連通支配集作為虛擬網(wǎng)絡(luò)骨干,以此來進(jìn)行數(shù)據(jù)聚合和網(wǎng)絡(luò)節(jié)點(diǎn)通信,實(shí)現(xiàn)網(wǎng)絡(luò)的廣播和路由。本文針對在Ad Hoc傳感器網(wǎng)絡(luò)中構(gòu)建最小連通支配集進(jìn)行了如下研究,通過分析現(xiàn)有算法,得出目前效果較好的求解連通支配集的方法是基于二階段的方法,因此本文針對其求解過程的兩個階段提出了三種改進(jìn)的算法。針對第一階段——求解MIS(極大獨(dú)立集)階段,本文分析了現(xiàn)有的基于協(xié)同覆蓋的最小連通支配集算法。該類算法的協(xié)同覆蓋思想雖然可以使問題接近最優(yōu)解,但也降低了覆蓋效率。本文對此進(jìn)行改進(jìn),采用新的支配點(diǎn)選擇方案,優(yōu)先從當(dāng)前支配節(jié)點(diǎn)的三跳鄰居中選擇下一個支配節(jié)點(diǎn),如果不存在,則從當(dāng)前支配節(jié)點(diǎn)的兩跳鄰居中選擇下一個支配節(jié)點(diǎn),使覆蓋盡可能少的存在交集,增大覆蓋效率。針對第二階段——斯坦納樹構(gòu)建階段,多數(shù)算法均采用貪心方式尋找斯坦納節(jié)點(diǎn),該類算法簡單但容易陷入局部最優(yōu)解。本文對此進(jìn)行改進(jìn),在斯坦納節(jié)點(diǎn)的選擇上了進(jìn)行了相應(yīng)的權(quán)值處理同時加入了檢測處理階段,即檢測是否存在冗余的節(jié)點(diǎn)。提出了兩種改進(jìn)的斯坦納樹構(gòu)建算法——IK-ST算法和ML-ST算法。進(jìn)一步降低了支配集的規(guī)模。仿真實(shí)驗(yàn)中,首先對比了IC-MIS算法和Rajiv Misra提出的算法,通過比較所求得的MIS的節(jié)點(diǎn)數(shù)目來衡量算法的優(yōu)劣,接著通過IK-ST和ML-ST算法優(yōu)化Rajiv Misra算法的斯坦納樹構(gòu)建階段,然后與其進(jìn)行比較,通過比較得到的斯坦納節(jié)點(diǎn)數(shù)目來衡量算法的優(yōu)劣。結(jié)果顯示本文提出的算法較先前的算法在優(yōu)化支配集規(guī)模上有了很大的改善。
[Abstract]:Ad Hoc sensor network is a kind of large-scale, self-organization, no infrastructure support and other characteristics of the network, can be used in various fields, has important practical significance. The network uses the connected dominating set as the backbone of the virtual network to aggregate the data and communicate with the network nodes to realize the broadcast and routing of the network. In this paper, the minimum connected dominating set in Ad Hoc sensor networks is studied as follows. By analyzing the existing algorithms, it is concluded that the most effective method to solve the connected dominating set is based on the two-stage method. Therefore, this paper proposes three improved algorithms for the two stages of the solution process. In this paper, we analyze the existing least connected dominating set algorithms based on cooperative covering for the first stage-solving MISS (maximal Independent set). The co-covering idea of this kind of algorithm can make the problem close to the optimal solution, but it also reduces the coverage efficiency. In this paper, a new dominating point selection scheme is adopted to select the next dominating node from the three-hop neighbor of the current dominant node, and if it does not exist, the next dominating node is selected from the two-hop neighbor of the current dominating node. Make the cover as little as possible exist intersection, increase coverage efficiency. In the second stage of Stener tree construction, most of the algorithms are greedy to find the Steiner node, which is simple but easy to fall into the local optimal solution. In this paper, the corresponding weights are processed on the selection of Steiner nodes, and the detection processing stage is added, that is, to detect the redundant nodes. Two improved Steiner tree construction algorithms, IK-ST algorithm and ML-ST algorithm, are proposed. The size of dominating set is further reduced. In the simulation experiment, the IC-MIS algorithm and the algorithm proposed by Rajiv Misra are compared at first. The advantages and disadvantages of the algorithm are measured by comparing the number of nodes in the obtained MIS. Then, the Stener tree construction phase of Rajiv Misra algorithm is optimized by IK-ST and ML-ST algorithms. Then compared with the algorithm, the algorithm is evaluated by comparing the number of Stener nodes. The results show that the proposed algorithm is much better than the previous algorithm in optimizing the size of dominating set.
【學(xué)位授予單位】：天津工業(yè)大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2016
【分類號】：TP212.9;TN929.5

【相似文獻(xiàn)】

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

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

2 張e，

本文編號：2004921