[發(fā)明專利]基于馬爾科夫決策過(guò)程的分段路由方法及一種網(wǎng)絡(luò)節(jié)點(diǎn)

在審

• 申請(qǐng)?zhí)枺?/td>: 201611190020.5
• 申請(qǐng)日: 2016-12-21
• 公開（公告）號(hào): CN106850425A
• 公開（公告）日: 2017-06-13
• 發(fā)明（設(shè)計(jì)）人: 王小明;張楊;張立臣;林亞光;王亮
• 申請(qǐng)（專利權(quán)）人: 陜西師范大學(xué)
• 主分類號(hào): H04L12/707
• 分類號(hào): H04L12/707;H04L12/721;H04L12/761
• 代理公司: 北京華創(chuàng)博為知識(shí)產(chǎn)權(quán)代理有限公司11551
• 代理人: 張波濤,管瑩

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

本公開涉及無(wú)線通信網(wǎng)絡(luò)中的通信路由，具體地講，涉及一種基于馬爾科夫決策過(guò)程的分段路由方法及一種網(wǎng)絡(luò)節(jié)點(diǎn)。

背景技術(shù)

移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)由于節(jié)點(diǎn)的移動(dòng)性，稀疏性，導(dǎo)致網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)時(shí)常發(fā)生變化，所以目的節(jié)點(diǎn)和源節(jié)點(diǎn)之間很少存在端到端的通信鏈路。這就使得傳統(tǒng)依賴于固定設(shè)施的蜂窩移動(dòng)網(wǎng)絡(luò)中采用“先路由-后傳輸”的工作模式統(tǒng)路由算法失效?？紤]到移動(dòng)機(jī)會(huì)網(wǎng)絡(luò)的弱連通性等特點(diǎn)，目前機(jī)會(huì)路由采用存儲(chǔ)-攜帶-轉(zhuǎn)發(fā)的工作模式。在這種工作模式下，當(dāng)節(jié)點(diǎn)接收到網(wǎng)絡(luò)中隨機(jī)相遇的節(jié)點(diǎn)轉(zhuǎn)發(fā)來(lái)的消息時(shí)，首先將消息存于自己的緩存中，并且攜帶消息繼續(xù)在網(wǎng)絡(luò)中隨機(jī)移動(dòng)并轉(zhuǎn)發(fā)給其他隨機(jī)相遇的節(jié)點(diǎn)，直到消息到達(dá)目的節(jié)點(diǎn)。在這種情況下，機(jī)會(huì)網(wǎng)絡(luò)中的路由算法作為實(shí)現(xiàn)間歇式連通環(huán)境下節(jié)點(diǎn)通信的理論基礎(chǔ)，具有十分重要的研究意義。但是在機(jī)會(huì)路由中節(jié)點(diǎn)如何選擇合適的轉(zhuǎn)發(fā)時(shí)機(jī)以及中繼節(jié)點(diǎn)，使得消息可以更快速的到達(dá)目的節(jié)點(diǎn)且節(jié)省更多的網(wǎng)絡(luò)資源，是目前機(jī)會(huì)路由研究的關(guān)鍵問題。

由于機(jī)會(huì)網(wǎng)絡(luò)的拓?fù)湟鬃兒凸?jié)點(diǎn)移動(dòng)的不確定性，給其路由算法的設(shè)計(jì)帶來(lái)挑戰(zhàn)。為了適應(yīng)機(jī)會(huì)網(wǎng)絡(luò)間斷、部分連接的特點(diǎn)，研究者提出了多種路由算法，其大致可以分為兩大類，單副本路由策略和多副本路由策略。單副本的路由策略是同一時(shí)間內(nèi)網(wǎng)絡(luò)中只保留消息的一個(gè)副本。此類路由的特點(diǎn)是網(wǎng)絡(luò)中由于副本的數(shù)量被嚴(yán)格的限制，導(dǎo)致網(wǎng)絡(luò)中消息的投遞率很低、延遲很大，消息不能快速準(zhǔn)確的到達(dá)目的節(jié)點(diǎn)。但是網(wǎng)絡(luò)副本被很好地控制，達(dá)到了節(jié)省網(wǎng)絡(luò)資源的目的?，F(xiàn)有幾種基于單副本的機(jī)會(huì)網(wǎng)絡(luò)節(jié)點(diǎn)轉(zhuǎn)發(fā)策略：(1)First Contact，該算法源節(jié)點(diǎn)將數(shù)據(jù)分組轉(zhuǎn)發(fā)給它每次遇到的下一跳節(jié)點(diǎn)；(2)Direct Delivery，該算法源節(jié)點(diǎn)僅在遇到目標(biāo)節(jié)點(diǎn)時(shí)才將數(shù)據(jù)分組轉(zhuǎn)發(fā)給下一節(jié)點(diǎn)；(3)隨機(jī)路由，以概率P將消息發(fā)送給其遇到的節(jié)點(diǎn)；(4)Seek and Focus，結(jié)合了隨機(jī)路由和基于效用路由的轉(zhuǎn)發(fā)策略；(5)Simbet，節(jié)點(diǎn)只將數(shù)據(jù)分組轉(zhuǎn)發(fā)給具備一定相似度的節(jié)點(diǎn)。

多副本的路由策略是每個(gè)節(jié)點(diǎn)可以按照規(guī)則攜帶多個(gè)消息副本。常見的多副本路由是Spray and Wait、Prophet、MaxProp、Epidemic。多副本路由策略由于副本數(shù)量的增加，在網(wǎng)絡(luò)中多個(gè)消息副本之間可以獨(dú)立的被傳遞至消息目的節(jié)點(diǎn)，相當(dāng)于單副本路由策略，多副本路由策略投遞率和消息延遲有著較大的提升，但是，副本數(shù)量的增多也會(huì)導(dǎo)致網(wǎng)絡(luò)負(fù)載的上升，網(wǎng)絡(luò)資源的消耗往往較大。

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

針對(duì)上述問題，本公開在考慮機(jī)會(huì)網(wǎng)絡(luò)中消息轉(zhuǎn)發(fā)時(shí)的投遞率和網(wǎng)絡(luò)負(fù)載之間的平衡的基礎(chǔ)上，結(jié)合多副本轉(zhuǎn)發(fā)策略，根據(jù)馬爾科夫決策過(guò)程提出了新的高效轉(zhuǎn)發(fā)因子，以提高投遞率、減少開銷和降低平均時(shí)延。

一方面，本公開提出了一種基于馬爾科夫決策過(guò)程的分段路由方法，所述方法包括下述步驟：

S100、判斷攜帶消息的節(jié)點(diǎn)周圍是否存在目的節(jié)點(diǎn)；

若所述攜帶消息的節(jié)點(diǎn)周圍存在目的節(jié)點(diǎn)，則執(zhí)行步驟S200；否則，執(zhí)行步驟S300；

S200、轉(zhuǎn)發(fā)消息給目的節(jié)點(diǎn)，完成消息轉(zhuǎn)發(fā)；

S300、判斷所述攜帶消息的節(jié)點(diǎn)所攜帶的消息副本數(shù)量是否為1；

若所述消息副本數(shù)量不為1，執(zhí)行步驟S400；否則，執(zhí)行步驟S500；

S400、在所述攜帶消息的節(jié)點(diǎn)隨機(jī)移動(dòng)過(guò)程中，將自身所攜帶的消息副本轉(zhuǎn)發(fā)給其隨機(jī)遇到的鄰居節(jié)點(diǎn)，使該鄰居節(jié)點(diǎn)成為一個(gè)攜帶消息的節(jié)點(diǎn)；且轉(zhuǎn)發(fā)消息副本的數(shù)量等于消息副本轉(zhuǎn)移概率與所述攜帶消息的節(jié)點(diǎn)所攜帶消息副本數(shù)量的乘積；

返回步驟S100；

S500、在所述攜帶消息的節(jié)點(diǎn)隨機(jī)移動(dòng)過(guò)程中，采用單副本路由轉(zhuǎn)發(fā)策略將所攜帶的消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)；

其中，所述消息副本轉(zhuǎn)移概率是由當(dāng)前時(shí)刻和下一時(shí)刻是否遞交消息副本確定的，消息副本轉(zhuǎn)移的過(guò)程符合馬爾科夫過(guò)程。

另一方面，本公開還涉及一種網(wǎng)絡(luò)節(jié)點(diǎn)，所述節(jié)點(diǎn)上包括第一判斷模塊、第一轉(zhuǎn)發(fā)模塊、第二判斷模塊、第二轉(zhuǎn)發(fā)模塊，第三轉(zhuǎn)發(fā)模塊，其中：

所述第一判斷模塊，被配置用于：當(dāng)節(jié)點(diǎn)上創(chuàng)建消息或收到消息失，判斷該節(jié)點(diǎn)周圍是否存在目的節(jié)點(diǎn)；若所述攜帶消息的節(jié)點(diǎn)周圍存在目的節(jié)點(diǎn)，轉(zhuǎn)入第一轉(zhuǎn)發(fā)模塊；否則，轉(zhuǎn)入第二判斷模塊；

所述第一轉(zhuǎn)發(fā)模塊，被配置用于：將所述節(jié)點(diǎn)攜帶的消息轉(zhuǎn)發(fā)給目的節(jié)點(diǎn)，完成消息轉(zhuǎn)發(fā)；

所述第二判斷模塊，被配置用于：判斷所述節(jié)點(diǎn)所攜帶的消息副本數(shù)量是否為1；若所述消息副本數(shù)量不為1，轉(zhuǎn)入第二轉(zhuǎn)發(fā)模塊；

否則，轉(zhuǎn)入第三轉(zhuǎn)發(fā)模塊；