基于Halin圖的無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)路徑規(guī)劃算法研究.pdf

1、無(wú)線傳感器網(wǎng)絡(luò)（Wireless Sensor Networks，WSN）由大量的傳感器節(jié)點(diǎn)組成，常被部署在環(huán)境惡劣、人跡罕至的地方，能量受限是人們?cè)谘芯繜o(wú)線傳感器網(wǎng)絡(luò)時(shí)不得不面臨的問(wèn)題。如何利用有限的節(jié)點(diǎn)能量，最大限度的發(fā)揮網(wǎng)絡(luò)的效能，延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間是工業(yè)界和學(xué)術(shù)界普遍關(guān)心的問(wèn)題。本文在研究分析了大量網(wǎng)絡(luò)生存時(shí)間優(yōu)化算法相關(guān)文獻(xiàn)的基礎(chǔ)上，提出了基于Halin圖的無(wú)線傳感器網(wǎng)絡(luò)移動(dòng)節(jié)點(diǎn)路徑規(guī)劃算法，借助移動(dòng)節(jié)點(diǎn)到傳感區(qū)域收集數(shù)據(jù)，減

2、少傳感器節(jié)點(diǎn)之間的通信量，均衡各節(jié)點(diǎn)的能量消耗，有效延長(zhǎng)網(wǎng)絡(luò)的生存時(shí)間。
　　算法首先將傳感區(qū)域劃分成若干個(gè)子區(qū)域，每?jī)蓚€(gè)子區(qū)域所包含的節(jié)點(diǎn)數(shù)最多相差1個(gè)，這樣可以保證每個(gè)子區(qū)域的整體能量消耗差異最小，從全局的角度均衡所有節(jié)點(diǎn)的能量消耗;接著根據(jù)韋伯選址思想，為每個(gè)子區(qū)域選取一個(gè)虛擬匯聚點(diǎn)，保證子區(qū)域內(nèi)所有節(jié)點(diǎn)到匯聚點(diǎn)的距離相等或近似相等，利用移動(dòng)節(jié)點(diǎn)到匯聚點(diǎn)收集數(shù)據(jù)，而不是通過(guò)多跳的方式傳輸數(shù)據(jù)，這樣可以從局部的角度進(jìn)一步均衡各

3、節(jié)點(diǎn)的能量消耗;為了最小化網(wǎng)絡(luò)的時(shí)延，同時(shí)降低節(jié)點(diǎn)因緩存數(shù)據(jù)和監(jiān)聽(tīng)信道而消耗的能量，算法將各虛擬匯聚點(diǎn)映射成一Halin圖，把移動(dòng)節(jié)點(diǎn)的路徑規(guī)劃問(wèn)題轉(zhuǎn)化成通過(guò) Halin圖扇收縮功能求解旅行商路徑問(wèn)題（Traveling Salesman Problem，TSP），從而得出移動(dòng)節(jié)點(diǎn)的最短移動(dòng)路徑。本文還設(shè)計(jì)了多移動(dòng)節(jié)點(diǎn)協(xié)同工作的算法，把 Halin的特征樹(shù)進(jìn)行分解，將到匯聚點(diǎn)收集數(shù)據(jù)的工作平均分擔(dān)給多個(gè)移動(dòng)節(jié)點(diǎn)共同完成，進(jìn)一步降低網(wǎng)絡(luò)時(shí)