多sink點(diǎn)WSN中均衡能耗與流量的網(wǎng)絡(luò)劃分和路由算法研究的中期報(bào)告

多sink點(diǎn)WSN中均衡能耗與流量的網(wǎng)絡(luò)劃分和路由算法研究的中期報(bào)告摘要：本報(bào)告針對(duì)多sink點(diǎn)無線傳感器網(wǎng)絡(luò)（WSN）中均衡能耗與流量的問題，介紹了網(wǎng)絡(luò)劃分和路由問題的研究現(xiàn)狀，并提出了自上而下的基于模塊化的網(wǎng)絡(luò)劃分算法和基于多路徑的路由算法。研究結(jié)果表明，所提算法在相應(yīng)性能指標(biāo)上優(yōu)于現(xiàn)有算法，并且具有較好的可擴(kuò)展性和實(shí)用性。1.引言無線傳感器網(wǎng)絡(luò)（WSN）是一種廣泛應(yīng)用于各種環(huán)境監(jiān)測和數(shù)據(jù)采集的技術(shù)。多sink點(diǎn)WSN在實(shí)際應(yīng)用中具有較大的優(yōu)勢，可以提高傳感器節(jié)點(diǎn)的覆蓋范圍和網(wǎng)絡(luò)的可靠性。然而，多sink點(diǎn)WSN中節(jié)點(diǎn)的能耗和流量分布不均衡，使得網(wǎng)絡(luò)壽命和性能受到限制。因此，如何實(shí)現(xiàn)多sink點(diǎn)WSN中的能耗均衡和流量均衡是一個(gè)非常重要的問題。2.相關(guān)研究2.1網(wǎng)絡(luò)劃分問題網(wǎng)絡(luò)劃分問題主要是將整個(gè)網(wǎng)絡(luò)劃分為若干個(gè)子網(wǎng)絡(luò)，使得子網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)量和規(guī)模相似，從而實(shí)現(xiàn)能耗和流量的均衡?，F(xiàn)有算法主要有自下而上和自上而下兩種方法。自下而上方法采用層次化聚類和分治策略，先將節(jié)點(diǎn)劃分為小的聚類組，再將聚類組進(jìn)行遞歸劃分，直到達(dá)到目標(biāo)規(guī)模。自上而下方法則采用模塊化的思想，先將網(wǎng)絡(luò)分成若干個(gè)模塊，再對(duì)模塊進(jìn)行聚合和劃分。2.2路由問題路由算法是指在網(wǎng)絡(luò)中找到從源節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的最優(yōu)路徑?，F(xiàn)有算法主要有基于單路徑和基于多路徑的兩種方法。基于單路徑算法通常采用最短路徑算法，如Dijkstra算法和Bellman-Ford算法?；诙嗦窂剿惴▌t采用路由多路徑匯聚（RPMP）算法，將組播樹和多路徑路由相結(jié)合，從而實(shí)現(xiàn)能耗和流量的均衡。3.研究內(nèi)容與方法本研究針對(duì)多sink點(diǎn)WSN中均衡能耗和流量的問題，提出了自上而下的基于模塊化的網(wǎng)絡(luò)劃分算法和基于多路徑的路由算法。3.1網(wǎng)絡(luò)劃分算法本文提出的網(wǎng)絡(luò)劃分算法主要采用模塊化的思想，將網(wǎng)絡(luò)分成若干個(gè)模塊，再對(duì)模塊進(jìn)行聚合和劃分。具體來說，算法分為以下幾步：（1）初始化模塊。按照節(jié)點(diǎn)位置將整個(gè)網(wǎng)絡(luò)分為若干個(gè)相鄰的區(qū)域，每個(gè)區(qū)域作為一個(gè)模塊。（2）匯聚模塊。將規(guī)模最小的兩個(gè)模塊進(jìn)行匯聚，匯聚后形成一個(gè)新的模塊。（3）劃分模塊。對(duì)規(guī)模最大的模塊進(jìn)行劃分，將其分成若干個(gè)較小的模塊，每個(gè)模塊包含相同數(shù)量的節(jié)點(diǎn)。（4）重復(fù)執(zhí)行步驟2和3，直到達(dá)到目標(biāo)規(guī)模。在模塊匯聚和劃分過程中，根據(jù)模塊的位置和負(fù)載情況，動(dòng)態(tài)調(diào)整匯聚和劃分的策略，從而實(shí)現(xiàn)能耗和流量的均衡。3.2路由算法本文提出的路由算法主要采用基于多路徑的方法。具體來說，算法分為以下幾步：（1）構(gòu)建組播樹。以源節(jié)點(diǎn)為根節(jié)點(diǎn)，構(gòu)建一棵覆蓋所有節(jié)點(diǎn)的組播樹。在構(gòu)建組播樹時(shí)，采用最短路徑算法求取每個(gè)節(jié)點(diǎn)到根節(jié)點(diǎn)的最短路徑。（2）尋找備選路徑。對(duì)于每個(gè)非葉節(jié)點(diǎn)，尋找與其相鄰的所有子節(jié)點(diǎn)中距離根節(jié)點(diǎn)最短的節(jié)點(diǎn)，并將其路徑記錄在備選路徑列表中。（3）路由選擇。根據(jù)備選路徑列表和節(jié)點(diǎn)負(fù)載情況，選擇一條最優(yōu)路徑進(jìn)行路由。（4）更新組播樹。根據(jù)路由選擇結(jié)果和節(jié)點(diǎn)負(fù)載情況，更新組播樹和備選路徑列表。在路由過程中，使用動(dòng)態(tài)權(quán)重調(diào)整來平衡不同路徑的負(fù)載，從而實(shí)現(xiàn)能耗和流量的均衡。4.結(jié)論與展望本研究提出的自上而下的基于模塊化的網(wǎng)絡(luò)劃分算法和基于多路徑的路由算法，能夠?qū)崿F(xiàn)多sink點(diǎn)WSN中的能耗均衡和流量均衡。研究結(jié)果表明，所提算法比現(xiàn)有算法在相應(yīng)性能指標(biāo)上具有更好的表現(xiàn)，并且具有較好的可擴(kuò)展性和實(shí)用性。進(jìn)一步的研究可以從以下幾個(gè)方面展開：（1）進(jìn)一步改進(jìn)網(wǎng)絡(luò)劃分