基于維諾圖和二分圖的水面移動(dòng)基站路徑規(guī)劃方法研究.pdf

1、近年來(lái)，隨著相關(guān)研究的不斷深入，無(wú)線傳感器網(wǎng)絡(luò)已成為一種十分重要的信息技術(shù)，目前已被廣泛應(yīng)用于生產(chǎn)、監(jiān)測(cè)、通信以及軍事等領(lǐng)域。水面?zhèn)鞲衅骶W(wǎng)絡(luò)作為無(wú)線傳感器網(wǎng)絡(luò)的一個(gè)重要分支，具有節(jié)點(diǎn)稀疏布置的特點(diǎn)，因此難以通過(guò)節(jié)點(diǎn)間的多跳路由匯聚數(shù)據(jù)，主要通過(guò)移動(dòng)基站來(lái)收集網(wǎng)絡(luò)中數(shù)據(jù)。在水面?zhèn)鞲衅骶W(wǎng)絡(luò)中，如何規(guī)劃出一條最優(yōu)的移動(dòng)基站路徑成為一個(gè)關(guān)鍵問(wèn)題。本文針對(duì)這一問(wèn)題進(jìn)行研究，提出了一種基于維諾圖和二分圖的水面移動(dòng)基站路徑規(guī)劃方法。大量實(shí)驗(yàn)結(jié)果表明該

2、方法可以有效規(guī)劃出水面?zhèn)鞲衅骶W(wǎng)絡(luò)中移動(dòng)基站的路徑，不僅可以完成全網(wǎng)數(shù)據(jù)收集任務(wù)，而且具有路徑長(zhǎng)度短、能量效率高和節(jié)點(diǎn)能耗均衡的優(yōu)點(diǎn)。
　　本文研究的主要內(nèi)容及主要?jiǎng)?chuàng)新之處在于:
　　(1)將維諾圖理論引入水面?zhèn)鞲衅骶W(wǎng)絡(luò)的移動(dòng)基站路徑規(guī)劃問(wèn)題中。應(yīng)用維諾圖理論對(duì)水面?zhèn)鞲衅骶W(wǎng)絡(luò)進(jìn)行建模，由傳感器節(jié)點(diǎn)集合構(gòu)造出相應(yīng)的維諾圖，利用維諾圖的性質(zhì)得到一系列數(shù)據(jù)收集“候選點(diǎn)”，即維諾圖頂點(diǎn)。與傳統(tǒng)方法中移動(dòng)基站前往傳感器節(jié)點(diǎn)處收集數(shù)據(jù)的模

3、式相比較，本文創(chuàng)新性的設(shè)計(jì)了移動(dòng)基站前往維諾圖頂點(diǎn)處收集傳感器節(jié)點(diǎn)數(shù)據(jù)的方法。通過(guò)理論和實(shí)驗(yàn)證明了在維諾圖頂點(diǎn)處收集傳感器節(jié)點(diǎn)數(shù)據(jù)，可以使傳感器節(jié)點(diǎn)能耗均衡。
　　(2)將圖論中的二分圖和支配集理論引入建立的維諾圖模型中。由維諾圖頂點(diǎn)和傳感器節(jié)點(diǎn)的關(guān)系構(gòu)造出二分圖，并定義了支配的概念，然后通過(guò)二分圖的形式來(lái)描述維諾圖頂點(diǎn)和傳感器節(jié)點(diǎn)間的支配關(guān)系;同時(shí)在借鑒支配集定義和求解方法的基礎(chǔ)上，定義了“最小有效支配集”的概念，并給出了最小有