[發(fā)明專利]一種基于二叉樹的網(wǎng)絡(luò)組織方法及裝置

在審

• 申請?zhí)枺?/td>: 202210418616.5
• 申請日: 2022-04-20
• 公開（公告）號: CN114978921A
• 公開（公告）日: 2022-08-30
• 發(fā)明（設(shè)計）人: 潘雨;張歡
• 申請（專利權(quán)）人: 北京中宸微電子有限公司
• 主分類號: H04L41/12
• 分類號: H04L41/12;H04L45/48;H04L45/745;H04B3/54;H04L101/622
• 代理公司: 北京中創(chuàng)云知識產(chǎn)權(quán)代理事務(wù)所(普通合伙) 11837
• 代理人: 龍明濤

本發(fā)明涉及一種基于二叉樹的網(wǎng)絡(luò)組織方法及裝置，包括將待組織網(wǎng)絡(luò)采用廣義樹結(jié)構(gòu)進行組織；將廣義樹結(jié)構(gòu)轉(zhuǎn)換為二叉樹結(jié)構(gòu)；基于二叉樹結(jié)構(gòu)，采用帶線索的二叉樹后序遍歷對指定網(wǎng)絡(luò)層級、葉子節(jié)點和最高層級葉子節(jié)點最大終端設(shè)備序號進行查找，以及對指定節(jié)點的子樹進行遍歷和刪除；采用帶線索的二叉樹中序遍歷對指定節(jié)點的父節(jié)點進行查找。采用本發(fā)明提供的網(wǎng)絡(luò)組織方法能夠更簡潔體現(xiàn)網(wǎng)絡(luò)拓撲的真實特性，不需要額外信息表述各個節(jié)點之前的關(guān)系，降低了數(shù)據(jù)結(jié)構(gòu)的復(fù)雜度；各個節(jié)點之間的關(guān)系可以通過高度抽象的二叉樹結(jié)構(gòu)模型來表達，實現(xiàn)了內(nèi)存占用率的極大降低。

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

本發(fā)明涉及電力通信技術(shù)領(lǐng)域，尤其涉及一種基于二叉樹的網(wǎng)絡(luò)組織方法及裝置。

背景技術(shù)

低壓電力線高速載波通信(High Speed Power Line Communication，以下簡稱“HPLC”)是一種新型的電力線通信技術(shù)，已經(jīng)廣泛應(yīng)用于國內(nèi)用電信息采集領(lǐng)域。結(jié)合高速無線通信(Radio Frequency，以下簡稱“HRF”)構(gòu)成的“HPLC+HRF”雙模通信，是在HPLC通信網(wǎng)絡(luò)基礎(chǔ)上增加了一個通信信道，并在鏈路層進行融合；實現(xiàn)HPLC和HRF的互補組網(wǎng)；而如何組織鏈路層的設(shè)備列表、路由表、鄰居表，特別是在增加了一個HRF信道之后，如何更高效的對數(shù)據(jù)進行增刪改查，成為新的問題。現(xiàn)有技術(shù)中，mesh通信網(wǎng)絡(luò)主節(jié)點、從節(jié)點在組織鏈路層數(shù)據(jù)和參數(shù)時，通過靜態(tài)數(shù)組、連續(xù)內(nèi)存、鏈表鏈接動態(tài)內(nèi)存等方式進行組織，根據(jù)需求同時生成設(shè)備列表、路由表、鄰居表的數(shù)據(jù)和參數(shù)結(jié)構(gòu)；采用的查詢方式通過遍歷的方式進行查找；占用內(nèi)存空間大且增刪改查效率低下。從而如何對HPLC+HRF雙模通信形式下的網(wǎng)絡(luò)結(jié)構(gòu)進行組織成為亟待解決的問題。

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

基于現(xiàn)有技術(shù)的上述情況，本發(fā)明的目的在于提供一種基于二叉樹的網(wǎng)絡(luò)組織方法及裝置，通過使用二叉樹等數(shù)據(jù)結(jié)構(gòu)對HPLC+HRF的鏈路層數(shù)據(jù)進行抽象和組織，進而完成對一些鏈路層數(shù)據(jù)結(jié)構(gòu)功能的高效實現(xiàn)，有效提升了代碼性能，在空間復(fù)雜度和時間復(fù)雜度上都有大幅度提升。

為達到上述目的，根據(jù)本發(fā)明的一個方面，提供了一種基于二叉樹的網(wǎng)絡(luò)組織方法，包括：

將待組織網(wǎng)絡(luò)采用廣義樹結(jié)構(gòu)進行組織；

將所述廣義樹結(jié)構(gòu)轉(zhuǎn)換為二叉樹結(jié)構(gòu)；

基于所述二叉樹結(jié)構(gòu)，采用帶線索的二叉樹后序遍歷對指定網(wǎng)絡(luò)層級、葉子節(jié)點和最高層級葉子節(jié)點最大終端設(shè)備序號進行查找，以及對指定節(jié)點的子樹進行遍歷和刪除；采用帶線索的二叉樹中序遍歷對指定節(jié)點的父節(jié)點進行查找。

進一步的，還包括：

使用終端設(shè)備序號和MAC地址為關(guān)鍵字的紅黑樹對數(shù)據(jù)進行組織；

利用所述關(guān)鍵字對指定終端設(shè)備序號和指定MAC地址進行查找。

進一步的，所述待組織網(wǎng)絡(luò)包括HPLC和HRF異構(gòu)網(wǎng)絡(luò)。

進一步的，所述廣義樹結(jié)構(gòu)中，根節(jié)點包括中央?yún)f(xié)調(diào)器CCO，根節(jié)點的下一級節(jié)點包括代理協(xié)調(diào)器PCO，代理協(xié)調(diào)器所在層級的下一級節(jié)點包括站點STA。

進一步的，所述二叉樹結(jié)構(gòu)中，每個節(jié)點有兩個子節(jié)點，將廣義樹結(jié)構(gòu)轉(zhuǎn)換為二叉樹結(jié)構(gòu)包括：

將廣義樹根節(jié)點的左節(jié)點設(shè)置為二叉樹根節(jié)點第一個左節(jié)點；

將廣義樹同一根節(jié)點下的其他所有鄰居節(jié)點依次設(shè)置為該節(jié)點的右節(jié)點；

將廣義樹根節(jié)點下第一級所有子節(jié)點的左節(jié)點分別設(shè)置為二叉樹下該節(jié)點的左節(jié)點；

將廣義樹根節(jié)點下第一級所有子節(jié)點的右節(jié)點分別設(shè)置為二叉樹下該節(jié)點的左節(jié)點的右節(jié)點。

進一步的，所述帶線索的二叉樹后序遍歷包括按照左子樹-右子樹-根節(jié)點的順序進行遍歷。