[發(fā)明專(zhuān)利]基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法及二叉樹(shù)的更新方法

有效

• 申請(qǐng)?zhí)枺?/td>: 202210022046.8
• 申請(qǐng)日: 2022-01-10
• 公開(kāi)（公告）號(hào): CN114363985B
• 公開(kāi)（公告）日: 2023-07-25
• 發(fā)明（設(shè)計(jì)）人: 王賀哲
• 申請(qǐng)（專(zhuān)利權(quán)）人: 黑龍江大學(xué)
• 主分類(lèi)號(hào): H04W40/04
• 分類(lèi)號(hào): H04W40/04;H04W40/10;H04L45/48
• 代理公司: 哈爾濱市松花江專(zhuān)利商標(biāo)事務(wù)所 23109
• 代理人: 董玉嬌

1.基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，該方法包括如下步驟：

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

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

S3、將各雙親節(jié)點(diǎn)與其所對(duì)應(yīng)的左孩子節(jié)點(diǎn)間、以及各雙親節(jié)點(diǎn)與其所對(duì)應(yīng)的右孩子節(jié)點(diǎn)間進(jìn)行連接，形成初始二叉樹(shù)；

S4、設(shè)置初始二叉樹(shù)中各邊的邊權(quán)重值；

S5、給初始二叉樹(shù)中的每一個(gè)節(jié)點(diǎn)分配一個(gè)初始位圖，并利用每個(gè)孩子節(jié)點(diǎn)的初始位圖中的信息、以及該孩子節(jié)點(diǎn)與其所對(duì)應(yīng)的雙親節(jié)點(diǎn)間的邊的邊權(quán)重值，對(duì)其所對(duì)應(yīng)的雙親節(jié)點(diǎn)的位圖進(jìn)行更新，從而完成對(duì)二叉樹(shù)的構(gòu)建。

2.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，步驟S1、根據(jù)各節(jié)點(diǎn)當(dāng)前的狀態(tài)，計(jì)算網(wǎng)絡(luò)中所有節(jié)點(diǎn)的權(quán)重值的實(shí)現(xiàn)方式為：

對(duì)于網(wǎng)絡(luò)中的任意節(jié)點(diǎn)node(i)，計(jì)算節(jié)點(diǎn)node(i)的權(quán)重值S(i)采用公式一實(shí)現(xiàn)，具體為，

S(i)＝α×Deltimes(i)+β×Buffsize(i)+γ×Battpower(i)????(公式一)；

其中，

Deltimes(i)為節(jié)點(diǎn)i轉(zhuǎn)發(fā)消息的次數(shù)；i為節(jié)點(diǎn)的編號(hào)；

Buffsize(i)為節(jié)點(diǎn)i剩余緩存大小；

Battpower(i)為節(jié)點(diǎn)i剩余電量的大小；

α、β、γ均為調(diào)節(jié)系數(shù)，且α+β+γ＝1。

3.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，步驟S2、根據(jù)網(wǎng)絡(luò)中各節(jié)點(diǎn)的權(quán)重值的排位確定各節(jié)點(diǎn)在二叉樹(shù)中的身份類(lèi)型的實(shí)現(xiàn)方式為：

S21、對(duì)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的權(quán)重值按照從小到大的順序進(jìn)行排序；

S22、按照節(jié)點(diǎn)序號(hào)從大到小的順序，依次令各節(jié)點(diǎn)作為雙親節(jié)點(diǎn)，且每個(gè)雙親節(jié)點(diǎn)對(duì)其左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)的選擇方式相同，從而完成對(duì)所有節(jié)點(diǎn)身份類(lèi)型的確定；

其中，每個(gè)雙親節(jié)點(diǎn)對(duì)其左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)的選擇方式具體為：

當(dāng)節(jié)點(diǎn)node(n)作為雙親節(jié)點(diǎn)時(shí)，選擇節(jié)點(diǎn)node(n-1)和節(jié)點(diǎn)node(n-2)分別作為雙親節(jié)點(diǎn)node(n)的左孩子節(jié)點(diǎn)和右孩子節(jié)點(diǎn)；n為節(jié)點(diǎn)的編號(hào)。

4.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，步驟S1中、節(jié)點(diǎn)轉(zhuǎn)發(fā)消息的次數(shù)為節(jié)點(diǎn)本身屬性。

5.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，步驟S4中、設(shè)置初始二叉樹(shù)中各邊的邊權(quán)重值的實(shí)現(xiàn)方式為：

將初始二叉樹(shù)中各雙親節(jié)點(diǎn)與其所對(duì)應(yīng)的左孩子節(jié)點(diǎn)間的邊的邊權(quán)重值設(shè)置為0，還將二叉樹(shù)中各雙親節(jié)點(diǎn)與其所對(duì)應(yīng)的右孩子節(jié)點(diǎn)間的邊的邊權(quán)重值設(shè)置為1。

6.根據(jù)權(quán)利要求1所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，每個(gè)節(jié)點(diǎn)的位圖中包括多個(gè)位置，且該多個(gè)位置由左至右依次排序，每個(gè)位置與該位置序號(hào)相同的節(jié)點(diǎn)相關(guān)聯(lián)；

每個(gè)節(jié)點(diǎn)中位置的個(gè)數(shù)與網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)相同；

每個(gè)位置包括兩個(gè)存儲(chǔ)單元，其中，

左邊存儲(chǔ)單元稱(chēng)為計(jì)數(shù)器，用于存儲(chǔ)當(dāng)前左邊存儲(chǔ)單元所在的節(jié)點(diǎn)到達(dá)與當(dāng)前左邊存儲(chǔ)單元所在的位置序號(hào)相同的節(jié)點(diǎn)的步數(shù)；

右邊的存儲(chǔ)單元稱(chēng)為足跡存儲(chǔ)器，用于存儲(chǔ)當(dāng)前右邊存儲(chǔ)單元所在的節(jié)點(diǎn)到達(dá)與當(dāng)前右邊存儲(chǔ)單元所在的位置序號(hào)相同的節(jié)點(diǎn)間邊的邊權(quán)重值。

7.根據(jù)權(quán)利要求6所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，其特征在于，每個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的初始位圖中的信息為：

與當(dāng)前節(jié)點(diǎn)序號(hào)相同的位置的計(jì)數(shù)器中存儲(chǔ)數(shù)字0；

與當(dāng)前節(jié)點(diǎn)序號(hào)相同的位置的足跡存儲(chǔ)器中存儲(chǔ)數(shù)字1；

當(dāng)前節(jié)點(diǎn)中剩余位置的計(jì)數(shù)器和足跡存儲(chǔ)器均存儲(chǔ)數(shù)字0。

8.二叉樹(shù)的更新方法，該二叉樹(shù)是采用權(quán)利要求1所述的基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法獲得的，其特征在于，該更新方法的具體過(guò)程為：

當(dāng)網(wǎng)絡(luò)中所構(gòu)建完成的二叉樹(shù)的生命時(shí)長(zhǎng)為T(mén)時(shí)，檢測(cè)網(wǎng)絡(luò)中所有節(jié)點(diǎn)的當(dāng)前狀態(tài)，利用基于節(jié)點(diǎn)權(quán)重構(gòu)建二叉樹(shù)的方法，對(duì)網(wǎng)絡(luò)中的所有節(jié)點(diǎn)進(jìn)行構(gòu)造，獲得新的二叉樹(shù)，從而完成對(duì)二叉樹(shù)的更新。