[發(fā)明專利]一種智能抄表系統(tǒng)無線網(wǎng)絡(luò)路由算法

在審

• 申請?zhí)枺?/td>: 201410258788.6
• 申請日: 2014-06-11
• 公開（公告）號: CN104065572A
• 公開（公告）日: 2014-09-24
• 發(fā)明（設(shè)計）人: 王宏;李世興;楊祖業(yè);李勇;王進(jìn)超
• 申請（專利權(quán)）人: 沈陽中科博微自動化技術(shù)有限公司
• 主分類號: H04L12/707
• 分類號: H04L12/707
• 代理公司: 沈陽優(yōu)普達(dá)知識產(chǎn)權(quán)代理事務(wù)所(特殊普通合伙) 21234
• 代理人: 俞魯江

1.一種智能抄表系統(tǒng)無線網(wǎng)絡(luò)路由算法，其特征在于：

采用吸收了Dijkstra算法思想的R-Dijkstra算法；

所述R-Dijkstra算法以Dijkstra算法為核心搜索算法，通過引入冗余度參數(shù)r，實現(xiàn)了路由路徑的冗余；

根據(jù)冗余度參數(shù)r，對待加入節(jié)點匯報的鄰居進(jìn)行選擇，然后對將每個選出的鄰居作為出發(fā)頂點，分別采用Dijkstra算法進(jìn)行對目的節(jié)點搜索，得出每條路徑后，最后將待加入節(jié)點分別添加到每條路徑的起點上，這樣就得出了冗余度r的路由路徑，這些路徑都是待加入節(jié)點到目的節(jié)點冗余的目標(biāo)代價最小的路由。

2.按照權(quán)利要求1所述一種智能抄表系統(tǒng)無線網(wǎng)絡(luò)路由算法，其特征在于：

冗余度參數(shù)r，表示每個節(jié)點在路由轉(zhuǎn)發(fā)數(shù)據(jù)時候可選擇的鄰居個數(shù)為r個；

網(wǎng)絡(luò)可以用一個有向圖模型G＝(V,E)來表達(dá)，其中V表示網(wǎng)絡(luò)中節(jié)點的集合，E為有向邊集合；網(wǎng)絡(luò)中每兩個節(jié)點之間的鏈接可以賦予權(quán)值w(i,j)，表示由節(jié)點i到節(jié)點j的鏈接權(quán)值；w(i,j)具體值的計算可以根據(jù)鏈路質(zhì)量、帶寬多個指標(biāo)計算獲得；將兩節(jié)點之間是否直接鏈接作為w(i,j)取值依據(jù)，有鏈接的鄰居之間的權(quán)值都為1，否則為無窮大；根據(jù)節(jié)點加入時匯報鄰居信息，然后采用R-Dijkstra算法，得出待加入節(jié)點的路由信息。

3.按照權(quán)利要求1所述的一種智能抄表系統(tǒng)無線網(wǎng)絡(luò)路由算法，其特征在于：

所述路徑都是待加入節(jié)點到目的節(jié)點冗余的目標(biāo)代價最小的路由，目標(biāo)代價可以考慮傳輸跳數(shù)、信號質(zhì)量、節(jié)點能量以及負(fù)載等因素的共同作用；從路由實時性考慮，在本算法中采用跳數(shù)作為目標(biāo)代價。

4.按照權(quán)利要求1的所述一種智能抄表系統(tǒng)無線網(wǎng)絡(luò)路由算法，其特征在于：算法的復(fù)雜度結(jié)論如下；

Dijkstra算法的復(fù)雜度主要在兩個循環(huán)中，因此Dijkstra算法的復(fù)雜度為O(n²)；R-Dijkstra算法在Dijkstra算法基礎(chǔ)上引入了冗余度參數(shù)r，以Dijkstra算法為基礎(chǔ)，進(jìn)行了r次循環(huán)；因此，R-Dijkstra算法的復(fù)雜度為O(r×n²)；

由于通常情況下r≥2，但n相對較大，則有r＜＜n，冗余度參數(shù)對算法復(fù)雜度的影響不是很嚴(yán)重。

5.按照權(quán)利要求1所述一種智能抄表系統(tǒng)無線網(wǎng)絡(luò)路由算法，其特征在于：

R-Dijkstra算法步驟如下；

步驟1：在r個鄰居節(jié)點中，選擇一個未被選擇過的節(jié)點作為出發(fā)頂點S，目的頂點為T，距離數(shù)組D用來表示S到其余各節(jié)點的傳輸跳數(shù)，路徑記錄數(shù)組為Path，其中D[i]表示S到節(jié)點i的最短距離，Path[i]表示S到節(jié)點i最短路徑需要經(jīng)過的節(jié)點；

步驟2：根據(jù)w(i,j)的值，初始化D、Path的值；

步驟3：從數(shù)組D中選擇值最小的且未被選擇過的頂點X，作為中間節(jié)點，其中X≠S，X≠T；

步驟4：令Z∈V且Z≠S,Z≠X，則數(shù)組D中S到Z的距離值為D[Z]，其中D的值用D[Z]_new來更新，按照以下策略：

D[Z]_new＝min(D[Z],D[X]+w(i,j))

如果發(fā)生D[Z]值發(fā)生變化，則相應(yīng)的Path[Z]做路徑記錄,Path[Z]＝X，表示S到Z的最短路徑需要經(jīng)過中間節(jié)點X，即S到X再到Z；

步驟5：重復(fù)步驟3、步驟4，直到所有D中的頂點都被選擇過；這時，所獲得的矩陣D中的值就是從S頂點出發(fā)到網(wǎng)絡(luò)中其余各點的最短距離，目的節(jié)點為T，找出Path[T]中記錄節(jié)點，將其輸出，然后將Path[T]中的結(jié)點作為新的目的節(jié)點賦給T，按照該操作方法，依次循環(huán)逆向輸出Path[T]中記錄的節(jié)點，直到不能取出新的目的節(jié)點T，然后輸出起始節(jié)點S，最后將上述輸出內(nèi)容反序，該路徑就是S到T最短路徑；

步驟6：如果r個鄰居都已經(jīng)被選擇過，則算法結(jié)束，否則返回步驟(1)。