[發(fā)明專(zhuān)利]一種多層無(wú)線(xiàn)網(wǎng)絡(luò)中基于場(chǎng)強(qiáng)獲得多條可靠通信路徑的方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201410230508.0
• 申請(qǐng)日: 2014-05-28
• 公開(kāi)（公告）號(hào): CN104093182B
• 公開(kāi)（公告）日: 2018-01-23
• 發(fā)明（設(shè)計(jì)）人: 馮子奇;李智
• 申請(qǐng)（專(zhuān)利權(quán)）人: 深圳市有方科技股份有限公司
• 主分類(lèi)號(hào): H04W40/04
• 分類(lèi)號(hào): H04W40/04
• 代理公司: 深圳市中聯(lián)專(zhuān)利代理有限公司44274
• 代理人: 李俊

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

本發(fā)明涉及一種多層無(wú)線(xiàn)網(wǎng)絡(luò)中基于場(chǎng)強(qiáng)獲得多條可靠通信路徑的方法，屬于無(wú)線(xiàn)通信技術(shù)領(lǐng)域。

背景技術(shù)

在通信技術(shù)領(lǐng)域多路徑計(jì)算方法應(yīng)用極為廣泛，其優(yōu)點(diǎn)在于提高了網(wǎng)絡(luò)的吞吐量和可靠性，同時(shí)多路徑的應(yīng)用也帶來(lái)了如何獲取多條最優(yōu)路徑的問(wèn)題。KSP算法，即K條最短路徑算法，是一種解決在網(wǎng)絡(luò)拓?fù)渲蝎@取指定源節(jié)點(diǎn)到目的節(jié)點(diǎn)的多條路徑問(wèn)題的算法，通過(guò)該算法可以在網(wǎng)絡(luò)拓?fù)渲蝎@得路徑權(quán)重和由小到大順序的K條路徑。K條最短路徑算法作為一種實(shí)用的算法，被廣泛應(yīng)用到通信路由計(jì)算、人工智能、經(jīng)濟(jì)理論研究的多種領(lǐng)域，具有很高的應(yīng)用價(jià)值。

在節(jié)點(diǎn)間單鏈路的拓?fù)渲校琄SP算法實(shí)現(xiàn)的總體流程如下，包括以下內(nèi)容：

調(diào)用Dijkstra算法計(jì)算第一優(yōu)路徑；

判斷計(jì)算出的路徑的數(shù)量是否滿(mǎn)足要求，如果滿(mǎn)足，則退出算法，停止計(jì)算；如果不滿(mǎn)足，繼續(xù)計(jì)算；

調(diào)用KSP算法，在節(jié)點(diǎn)間單鏈路的拓?fù)渖希?jì)算下一優(yōu)路徑，進(jìn)行判斷。

由于需要多次嵌套使用Dijkstra算法，KSP算法普遍存在算法時(shí)間復(fù)雜度和空間復(fù)雜度高的問(wèn)題。

無(wú)線(xiàn)多層網(wǎng)絡(luò)普遍應(yīng)用于無(wú)線(xiàn)抄表、無(wú)線(xiàn)傳感器網(wǎng)絡(luò)等諸多領(lǐng)域。由于面臨節(jié)點(diǎn)間通信不穩(wěn)定和通信環(huán)境變化等限制，需要在路由的計(jì)算過(guò)程中，提供多條優(yōu)選可替代路由，以在選定路由上通信鏈路失敗后，提供可替換的路由以進(jìn)行再次的數(shù)據(jù)傳輸過(guò)程。由于無(wú)線(xiàn)節(jié)點(diǎn)要滿(mǎn)足低功耗、低成本等需求，無(wú)線(xiàn)節(jié)點(diǎn)大都存在系統(tǒng)資源有限的問(wèn)題，因此需要一種時(shí)間復(fù)雜度與空間復(fù)雜度低的多條路由選擇算法。

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

本發(fā)明的目的是提出一種多層無(wú)線(xiàn)網(wǎng)絡(luò)中基于場(chǎng)強(qiáng)獲得多條可靠通信路徑的方法，在滿(mǎn)足性能的前提下，解決計(jì)算空間復(fù)雜度過(guò)大問(wèn)題。在計(jì)算過(guò)程中通過(guò)計(jì)算正反雙方向最短路徑，對(duì)雙方向最短路徑求和后得到次優(yōu)路徑，并對(duì)所得路徑進(jìn)行試探。

本發(fā)明提出的多層無(wú)線(xiàn)網(wǎng)絡(luò)中基于場(chǎng)強(qiáng)獲得多條可靠通信路徑的方法，包括以下各步驟：

(1)在網(wǎng)絡(luò)中選取源節(jié)點(diǎn)和目的節(jié)點(diǎn)，接收短程無(wú)線(xiàn)網(wǎng)絡(luò)中發(fā)送端發(fā)出的射頻信號(hào)，計(jì)算各節(jié)點(diǎn)間通信場(chǎng)強(qiáng)，節(jié)點(diǎn)與其它各節(jié)點(diǎn)的通信場(chǎng)強(qiáng)組成場(chǎng)強(qiáng)序列記為Q_M，多個(gè)節(jié)點(diǎn)場(chǎng)強(qiáng)序列組成鄰居場(chǎng)強(qiáng)表，如果節(jié)點(diǎn)之間沒(méi)有鏈路直接相連，則不在鄰居場(chǎng)強(qiáng)表中進(jìn)行記錄，計(jì)算中其場(chǎng)強(qiáng)值設(shè)為“無(wú)窮大”；

(2)通過(guò)多點(diǎn)最短路徑算法計(jì)算源節(jié)點(diǎn)到其他各節(jié)點(diǎn)的正向最優(yōu)路徑集合和正向最優(yōu)路徑權(quán)值集合，其中，由源節(jié)點(diǎn)到目的節(jié)點(diǎn)的計(jì)算結(jié)果為正向最優(yōu)路徑和正向最優(yōu)路徑權(quán)值。

(3)通過(guò)多點(diǎn)最短路徑算法計(jì)算得到目的節(jié)點(diǎn)到各節(jié)點(diǎn)的反向最優(yōu)路徑集合和反向最優(yōu)路徑權(quán)值集合，其中，由目的節(jié)點(diǎn)到源節(jié)點(diǎn)的計(jì)算結(jié)果為反向最優(yōu)路徑和反向最優(yōu)路徑權(quán)值；

(4)計(jì)算源節(jié)點(diǎn)到除目的節(jié)點(diǎn)外各節(jié)點(diǎn)的正向最優(yōu)路徑權(quán)值與目的節(jié)點(diǎn)到對(duì)應(yīng)各節(jié)點(diǎn)的反向最優(yōu)路徑權(quán)值的權(quán)值和，權(quán)值和結(jié)果最優(yōu)的路徑即為次優(yōu)路徑；

(5)通過(guò)對(duì)正向最優(yōu)路徑，反向最優(yōu)路徑和次優(yōu)路徑進(jìn)行試探結(jié)果調(diào)整路徑權(quán)值，試探成功路徑權(quán)值增大，試探失敗路徑權(quán)值減小，即得到按路徑權(quán)值排序的多條路由。

上述多點(diǎn)最短路徑算法，所述包含起始節(jié)點(diǎn)、結(jié)束節(jié)點(diǎn)、中間節(jié)點(diǎn)，其特征在于：

(1)為無(wú)線(xiàn)網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)建立一組狀態(tài)記錄，狀態(tài)記錄包括前序參數(shù)、路徑權(quán)重參數(shù)、跳數(shù)參數(shù)、標(biāo)號(hào)參數(shù)；其中，前序參數(shù)表示當(dāng)前節(jié)點(diǎn)之前的節(jié)點(diǎn)，路徑權(quán)重參數(shù)表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑權(quán)重，跳數(shù)參數(shù)表示從起始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的跳數(shù)，標(biāo)號(hào)參數(shù)表示節(jié)點(diǎn)的狀態(tài)，每個(gè)節(jié)點(diǎn)的標(biāo)號(hào)參數(shù)都處在“永久”或“暫時(shí)”狀態(tài)，當(dāng)一個(gè)節(jié)點(diǎn)的標(biāo)號(hào)參數(shù)為“永久”后，將不再改變；

(2)初始化所有節(jié)點(diǎn)的狀態(tài)記錄，將各節(jié)點(diǎn)的路徑權(quán)重參數(shù)設(shè)為“無(wú)窮小”，標(biāo)號(hào)參數(shù)設(shè)為“暫時(shí)”，跳數(shù)參數(shù)設(shè)為0；

(3)將起始節(jié)點(diǎn)的標(biāo)號(hào)參數(shù)更改為“永久”狀態(tài)。

(4)更新與起始節(jié)點(diǎn)直接相連的所有標(biāo)號(hào)參數(shù)為“暫時(shí)”的節(jié)點(diǎn)狀態(tài)記錄，讀取鄰居場(chǎng)強(qiáng)表中起始節(jié)點(diǎn)到所有標(biāo)號(hào)參數(shù)為“暫時(shí)”的節(jié)點(diǎn)的場(chǎng)強(qiáng)值，按照路徑權(quán)重計(jì)算方法更新路徑權(quán)重參數(shù)，并更新前序參數(shù)和跳數(shù)參數(shù)；

(5)在上述標(biāo)號(hào)參數(shù)為“暫時(shí)”的節(jié)點(diǎn)中選擇距離起始節(jié)點(diǎn)V_S的路徑權(quán)重最高的節(jié)點(diǎn)。將這個(gè)節(jié)點(diǎn)作為新的起始節(jié)點(diǎn)，并重復(fù)過(guò)程(3)至(5)，當(dāng)所有節(jié)點(diǎn)的標(biāo)號(hào)參數(shù)均為“永久”后，從結(jié)束節(jié)點(diǎn)開(kāi)始依次提取前序參數(shù)到起始節(jié)點(diǎn)為止，這個(gè)節(jié)點(diǎn)列表便是從起始節(jié)點(diǎn)到結(jié)束節(jié)點(diǎn)的最佳路徑；結(jié)束節(jié)點(diǎn)的路徑權(quán)重參數(shù)即為最優(yōu)路徑權(quán)值。

上述路徑權(quán)重計(jì)算方法，其特征在于：