[發(fā)明專利]一種遞增式遞歸計算約束下的路由方法

有效

• 申請?zhí)枺?/td>: 201611085481.6
• 申請日: 2016-11-30
• 公開（公告）號: CN108135019B
• 公開（公告）日: 2019-12-20
• 發(fā)明（設(shè)計）人: 郭鵬;劉雪峰
• 申請（專利權(quán)）人: 華中科技大學(xué)
• 主分類號: H04W40/02
• 分類號: H04W40/02;H04W84/18
• 代理公司: 42201 華中科技大學(xué)專利中心
• 代理人: 趙偉

本發(fā)明公開了一種遞增式遞歸計算約束下的路由方法，包括如下步驟：將拓?fù)鋱D中離匯聚節(jié)點最遠(yuǎn)的節(jié)點作為起始節(jié)點，起始節(jié)點到匯聚節(jié)點的最短路徑作為初始路徑；對節(jié)點nⁱ的每個不在路徑P^i?1上的鄰居，將節(jié)點nⁱ到該鄰居的邊、以及該鄰居到匯聚節(jié)點的最短路徑相連得到第i連接路徑；根據(jù)各鄰居節(jié)點所對應(yīng)的第i連接路徑的全網(wǎng)總通信開銷挑出節(jié)點nⁱ的最佳鄰居，以最佳鄰居對應(yīng)的第i連接路徑來更新路徑P^i?1，獲得第i處理路徑Pⁱ；重復(fù)該處理直到遍歷初始路徑，獲得最終處理路徑；對處在最終處理路徑上的節(jié)點以最終處理路徑作為該節(jié)點傳送網(wǎng)內(nèi)處理結(jié)果的路由；對不在最終處理路徑上的節(jié)點，以該節(jié)點與最終處理路徑上最佳節(jié)點之間的最短路徑作為該節(jié)點傳送源數(shù)據(jù)的路由。

技術(shù)領(lǐng)域

本發(fā)明屬于計算機(jī)網(wǎng)絡(luò)技術(shù)領(lǐng)域，更具體地，涉及一種遞增式遞歸計算約束下的路由方法。

背景技術(shù)

在很多基于無線傳感器網(wǎng)絡(luò)的數(shù)據(jù)匯聚和融合應(yīng)用中，采用網(wǎng)內(nèi)處理技術(shù)是有效降低無線傳感器網(wǎng)絡(luò)的通信開銷的方式。運用網(wǎng)內(nèi)處理技術(shù)，各個傳感器節(jié)點不再是中繼原始數(shù)據(jù)給匯聚節(jié)點，而是對收到的數(shù)據(jù)進(jìn)行一定的計算，然后將計算后的結(jié)果中繼給下一跳節(jié)點，由此可顯著降低傳輸開銷。

我們期望：采用網(wǎng)內(nèi)處理的無線傳感器網(wǎng)絡(luò)中的匯聚節(jié)點最終所獲得的數(shù)據(jù)結(jié)果，能與未采用網(wǎng)內(nèi)處理的無線傳感器網(wǎng)絡(luò)中的匯聚節(jié)點對所有原始數(shù)據(jù)的處理結(jié)果一致或接近，這樣，進(jìn)行網(wǎng)內(nèi)處理才具有替代直接傳輸原始數(shù)據(jù)這種方式的意義。因此，需要將在本應(yīng)在匯聚節(jié)點執(zhí)行的計算任務(wù)無失真地拆分并分配到網(wǎng)絡(luò)中的各個節(jié)點上執(zhí)行；而路由規(guī)劃則是降低通信總開銷的關(guān)鍵。

發(fā)明內(nèi)容

針對現(xiàn)有技術(shù)的以上缺陷或改進(jìn)需求，本發(fā)明提供了一種遞增式遞歸計算約束下的路由方法，其目的在于為網(wǎng)絡(luò)中的節(jié)點規(guī)劃一條路由，使得路由上的節(jié)點根據(jù)分配的計算子任務(wù)，將收到的數(shù)據(jù)與本地數(shù)據(jù)進(jìn)行處理，并按照規(guī)劃的路由將處理的結(jié)果傳給下一個節(jié)點，以降低網(wǎng)絡(luò)通信總開銷。

為實現(xiàn)上述目的，按照本發(fā)明的一個方面，提供了一種遞增式遞歸計算約束下的路由方法，包括如下步驟：

(1)根據(jù)網(wǎng)絡(luò)各節(jié)點的連接關(guān)系建立拓?fù)鋱DG＝(V，E)；其中，V為網(wǎng)絡(luò)節(jié)點的集合，E為節(jié)點之間的直接連接關(guān)系(邊)的集合；

(2)將拓?fù)鋱DG中離匯聚節(jié)點S最遠(yuǎn)的節(jié)點作為路由的起始節(jié)點，記為n¹；將起始節(jié)點n¹到匯聚節(jié)點S的最短路徑作為網(wǎng)內(nèi)處理的初始路徑，初始路徑P¹＝{n¹,n²,…nⁱ,…,S}，其中nⁱ為初始路徑P¹上第i個節(jié)點；將i初始化為1；

(3)對節(jié)點nⁱ的每個不在路徑Pⁱ上的鄰居，將節(jié)點nⁱ到該鄰居的邊、以及該鄰居到匯聚節(jié)點S的最短路徑相連得到第i連接路徑；

根據(jù)所述各鄰居節(jié)點所對應(yīng)的第i連接路徑的全網(wǎng)總通信開銷，從所有鄰居節(jié)點中挑出節(jié)點nⁱ的最佳鄰居，以所述最佳鄰居對應(yīng)的第i連接路徑來更新路徑Pⁱ，獲得第i網(wǎng)內(nèi)處理路徑Pⁱ⁺¹；

(4)令i＝i+1，并重復(fù)步驟(3)，直到nⁱ為當(dāng)前路徑Pⁱ中的倒數(shù)第二個節(jié)點，此時的路徑Pⁱ即為最終網(wǎng)內(nèi)處理路徑P’；

(5)對所有處在最終網(wǎng)內(nèi)處理路徑P’上的節(jié)點，以最終網(wǎng)內(nèi)處理路徑P’作為該節(jié)點傳送網(wǎng)內(nèi)處理結(jié)果的路由；