[發(fā)明專利]基于節(jié)點權重構建二叉樹的方法及二叉樹的更新方法

有效

• 申請?zhí)枺?/td>: 202210022046.8
• 申請日: 2022-01-10
• 公開（公告）號: CN114363985B
• 公開（公告）日: 2023-07-25
• 發(fā)明（設計）人: 王賀哲
• 申請（專利權）人: 黑龍江大學
• 主分類號: H04W40/04
• 分類號: H04W40/04;H04W40/10;H04L45/48
• 代理公司: 哈爾濱市松花江專利商標事務所 23109
• 代理人: 董玉嬌

基于節(jié)點權重構建二叉樹的方法及二叉樹的更新方法，屬于無線多跳網(wǎng)絡領域。解決了現(xiàn)有無線多跳網(wǎng)絡路由方法中采用隨機的方式構造的二叉樹，存在雙親節(jié)點的緩存資源以及電量資源容易被耗盡，且存在消息的遞交率低，影響網(wǎng)絡整體性能的缺陷。本發(fā)明先根據(jù)各節(jié)點當前的狀態(tài)，計算網(wǎng)絡中所有節(jié)點的權重值；再根據(jù)網(wǎng)絡中各節(jié)點的權重值的排位確定節(jié)點在二叉樹中的身份類型；將各雙親節(jié)點與其所對應的左孩子節(jié)點間、以及各雙親節(jié)點與其所對應的右孩子節(jié)點間進行連接，形成初始二叉樹；再設置初始二叉樹中各邊的邊權重值；最后給初始二叉樹中各節(jié)點分配初始位圖，更新雙親節(jié)點的位圖信息，從而完成對二叉樹的構建。本發(fā)明主要應用在無線多跳網(wǎng)絡領域。

技術領域

本發(fā)明屬于無線多跳網(wǎng)絡領域，具體涉及一種基于節(jié)點權重構建二叉樹的方法和無線多跳網(wǎng)中二叉樹的更新方法。

背景技術

隨著無線通信技術的快速發(fā)展以及智能終端設備的迅速普及，人們對無線網(wǎng)絡的要求也不斷提高。無線多跳網(wǎng)絡以其分布式運行、立體化組網(wǎng)以及擴展性強等特點成為連接人與物、人與人和物與物之間的橋梁，已被廣泛應用于日常生活的各個領域。從無線多跳網(wǎng)絡誕生以來，路由協(xié)議作為組網(wǎng)的關鍵技術之一，一直受到國內(nèi)外研究人員的高度關注。在無線多跳網(wǎng)絡中，節(jié)點在傳遞消息過程中通常不依賴預先部署的基礎設施，而是讓節(jié)點充當路由器，將消息傳輸?shù)侥康墓?jié)點。然而，由于無線多跳網(wǎng)絡自身獨有的一些特點，例如：節(jié)點的移動性、網(wǎng)絡拓撲動態(tài)變化、節(jié)點資源有限以及帶寬有限等為路由方法的設計帶來了極大的挑戰(zhàn)。因此，面向無線多跳網(wǎng)絡設計高效的路由方法，以此提高網(wǎng)絡性能是無線多跳網(wǎng)絡研究過程中亟需解決的關鍵問題之一。

目前國內(nèi)外研究人員已經(jīng)針對無線多跳網(wǎng)絡提出了大量的路由方法，其中Derakhshanfard等人提出一種Opportunistic?routing?in?wireless?networks?usingbitmap-based?weighted?tree方法，該方法利用網(wǎng)絡中的節(jié)點隨機構造一棵二叉樹，將邊權重值0和1分別分配給二叉樹的雙親節(jié)點與左孩子節(jié)點連接的邊和雙親節(jié)點與右孩子節(jié)點連接的邊。給二叉樹中的每一個節(jié)點分配初始位圖，并通過從孩子節(jié)點收集相應的位圖信息以及與孩子節(jié)點關聯(lián)的邊的邊權重值更新每個雙親節(jié)點的位圖信息。當有消息發(fā)送到二叉樹中的某個節(jié)點時，將該消息以位圖的形式存儲在二叉樹節(jié)點中，并將消息的位圖與其所在節(jié)點的位圖的對應位相乘。如果對應位相乘結果均為0，則目的節(jié)點不在當前節(jié)點子目錄中。此時，消息發(fā)送到更高的并且能夠到達目的節(jié)點的雙親節(jié)點。如果對應位相乘結果不均為0，則目的節(jié)點在當前節(jié)點子目錄中，根據(jù)位圖對應位相乘得到的結果，選擇下一個中繼節(jié)點。

該方法能夠有效的保障網(wǎng)絡的遞交率以及時延，但是該方法在構造二叉樹時，采用隨機的方式構造二叉樹容易使得緩存資源或者電量資源較少的節(jié)點充當雙親節(jié)點。在消息被轉發(fā)的過程中，雙親節(jié)點轉發(fā)消息的次數(shù)要多于孩子節(jié)點，使得雙親節(jié)點的緩存資源以及電量資源很容易被耗盡，從而影響網(wǎng)絡的整體性能。除此之外，在構造二叉樹的過程中，沒有將節(jié)點轉發(fā)消息的次數(shù)作為構造二叉樹的依據(jù)，容易使得轉發(fā)消息能力不高的節(jié)點作為根節(jié)點或雙親節(jié)點，從而降低了消息的遞交率并增加時延。因此，針對以上缺陷亟需解決。

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

本發(fā)明目的是為了解決現(xiàn)有無線多跳網(wǎng)絡路由方法中采用隨機的方式構造的二叉樹，存在雙親節(jié)點的緩存資源以及電量資源容易被耗盡，且存在消息的遞交率低，影響網(wǎng)絡整體性能的缺陷；因此，本發(fā)明提供了一種基于節(jié)點權重構建二叉樹的方法及二叉樹的更新方法。

基于節(jié)點權重構建二叉樹的方法，該方法包括如下步驟：

S1、根據(jù)各節(jié)點當前的狀態(tài)，計算網(wǎng)絡中所有節(jié)點的權重值；其中，節(jié)點當前的狀態(tài)包括節(jié)點轉發(fā)消息的次數(shù)、節(jié)點剩余緩存和節(jié)點剩余電量；所述的網(wǎng)絡為無線多跳網(wǎng)絡；

S2、根據(jù)網(wǎng)絡中各節(jié)點的權重值的排位確定各節(jié)點在二叉樹中的身份類型；其中，節(jié)點身份類型包括雙親節(jié)點和孩子節(jié)點，且孩子節(jié)點包括左孩子節(jié)點和右孩子節(jié)點；