Multi-Channel Network Construction Algorithm Based on Hierarchical Virtual Clustering
-
摘要: 针对无线自组网遭受强电磁干扰造成节点间感知到的可用信道存在差异且组网困难的问题，该文提出一种基于分层虚拟簇的多信道组网方法，以实现网络可靠性提升与干扰控制。首先，基于各相邻节点感知到的公共信道邻居比信息构建相似度指标，并基于该指标对网络模块度函数进行改进，形成以网络模块度最大的分簇网络；其次，通过先控制再连通的方式选举簇头节点和网关节点，并采用生成树方法构建基于R-跳连通控制集(CDS)的虚拟骨干网链路为簇间节点提供路由转发服务；最后，提出受限图着色方法对簇内与簇间信道进行分配，以减小簇内与簇间通信存在的同频干扰。仿真结果表明，所提算法构建的分簇网络模块度更高，且在平均簇规模和干扰控制等方面能够取得更优的性能。Abstract: Considering the differential channels sensed by nodes and difficult network construction due to strong electromagnetic interference in wireless ad hoc networks, a multi-channel network construction algorithm based on hierarchical virtual clustering is proposed to realize network reliability improvement and interference control. Firstly, the similarity index is defined by the ratio of neighbors with common channels sensed by the adjacent nodes, which is utilized further to formulate the network modularity function. A clustering network is constructed with the largest modularity. Then, the cluster head nodes and gateway nodes are selected by the way of control before connection. The virtual backbone network controlled by R-hop Connected Dominating Set (CDS) is established by using the spanning tree method to provide routing and forwarding services for inter-cluster nodes. Finally, a restricted graph coloring method is proposed to implement inter-cluster and intra-cluster channel allocation to reduce the co-channel interference. Simulation results show that the proposed algorithm can obtain higher network modularity than the baseline schemes, while shows performance advantages in average cluster size and interference control.
-
算法1 基于公共信道邻居比的簇网络聚类算法 (1) 输入：各节点感知到的可用信道集合 $ {\bf{C}}{{\bf{H}}_i} $、地理位置、通
信半径 $ R $等信息;(2) 输出：各簇网络成员，各簇网络的公共信道 ${\bf{CCH}}$。 (3) 初始化：簇网络集合为 $ {\bf{CN}} $，节点集合为 $ {\boldsymbol{V}} $，网络的模块度
函数为 $ Q = 0 $;(4) while 分簇结构无变化do (5) 初始化一个节点为一个簇网络，利用式(1)计算任意两相邻
节点间的相似度；(6) while 没有节点加入新的簇网络do (7) for节点 $ i \in {\boldsymbol{V}} $且 $ i \in C $ do (8) 计算将节点 $ i $加入到簇网络 $ C' $带来的模块度增量，并
找到模块度增量最大的簇网络 $ C' $；(9) if $ \Delta {Q_{i \to C'}} > 0 $ then (10) 更新簇网络 $ C $和 $ C' $中的成员节点； (11) end if (12) end for (13) end while (14) 计算网络的模块度 $ Q $； (15) 将簇网络抽象为一个虚拟节点，更新网络的节点集合与节
点间的相似度指标；(16) end while 
下载: 导出CSV
算法2 基于R-跳连通控制集的最小生成树骨干网构建算法 (1) 输入：各簇网络成员节点，各节点感知到的邻居节点集； (2) 输出：骨干网链路。 (3) 初始化：簇头节点集合为 ${\bf{CHN}}$，树节点集合为 ${\bf{TN}}$； (4) 通过式(5)找到所有簇头节点并存入到簇头节点集合 ${\bf{CHN}}$； (5) while簇头节点集合 ${\bf{CHN}}$为非空集do (6) if 树节点集合 ${\bf{TN}}$为空集then (7) 找到 ${\bf{CHN}}$集合中距离所有成员节点最近的两个簇头节点
$i$和 $j$， $i,j \in {\bf{CHN}}$；(8) else (9) 找到 ${\bf{CHN}}$集合中距离所有成员节点最近的簇头节点 $i$与
树节点集合 ${\bf{TN}}$中的任意节点 $j$， $ i \in {\bf{CHN}},j \in {\bf{TN}} $；(10) end if (11) 找到 $i$与 $j$节点间所有 $H(H > R)$跳以内的路径集合； (12) while未找到其他成员节点距离 $i,j$节点间链路为 $R$跳的
可达路径do(13) 统计其他成员节点到各路径节点间的平均最短链路长
度，并选择平均最短链路长度小于等于 $R$跳的路径作为
最终路径；(14) 将最终路径经过的节点存入树集合 ${\bf{TN}}$； (15) 若 $ i \in {\bf{CHN}} $或 $j \in {\bf{CHN}}$，则在簇头节点集合 ${\bf{CHN}}$中去
除该簇头节点；(16) end while (17) end while
下载: 导出CSV
算法3 基于受限图着色的分层虚拟簇网络信道分配算法 (1) 输入：虚拟簇网络连通图 $ {\boldsymbol{G'}} $，各虚拟簇公共信道，簇头节点
可用信道，网关节点可用信道；(2) 输出：冲突图中各节点的着色方案。 (3) 将虚拟簇网络连通图 ${\boldsymbol{G'}}$转换为冲突图； (4) 统计冲突图中各节点的可用颜色数，并按照颜色数升序的方
式对节点进行排序；(5) while 还有顶点未着色do (6) if 顶点 $n$仅有1种颜色可用then (7) 采用该颜色对节点 $n$和与 $n$互不冲突的节点进行着色； (8) else if 统计 $n$的邻居节点已使用的颜色then (9) 选择未使用或使用次数最少的颜色 $m$对节点 $n$进行着色； (10) 采用颜色 $m$对与节点 $n$互不冲突的节点着色； (11) end if (12) end while
下载: 导出CSV
-
[1] 郭明. 关于智能化战争的基本认知[J]. 人民论坛·学术前沿, 2021(10): 14–21. doi: 10.16619/j.cnki.rmltxsqy.2021.10.002GUO Ming. Basic understandings of the intelligent wars[J]. Frontiers, 2021(10): 14–21. doi: 10.16619/j.cnki.rmltxsqy.2021.10.002 [2] ELMASRY G F. A comparative review of commercial vs. tactical wireless networks[J]. IEEE Communications Magazine, 2010, 48(10): 54–59. doi: 10.1109/MCOM.2010.5594677 [3] AGRAWAL R, FAUJDAR N, ROMERO C A T, et al. Classification and comparison of ad hoc networks: A review[J]. Egyptian Informatics Journal, 2023, 24(1): 1–25. doi: 10.1016/j.eij.2022.10.004 [4] 黄晓舸, 何勇, 陈前斌, 等. 无人机群辅助的数据采集能耗优化方法[J]. 电子与信息学报, 2023, 45(6): 2054–2062. doi: 10.11999/JEIT220554HUANG Xiaoge, HE Yong, CHEN Qianbin, et al. Optimization method for energy consumption in data acquisition assisted by UAV swarms[J]. Journal of Electronics & Information Technology, 2023, 45(6): 2054–2062. doi: 10.11999/JEIT220554 [5] GUO Jingjing, GAO Huamin, LIU Zhiquan, et al. ICRA: An intelligent clustering routing approach for UAV ad hoc networks[J]. IEEE Transactions on Intelligent Transportation Systems, 2023, 24(2): 2447–2460. doi: 10.1109/TITS.2022.3145857 [6] KELAGADI H M and PRIYATAMKUMAR G. Energy efficient clustering and topology management scheme for wireless sensor networks[J]. International Journal of Communication Networks and Distributed Systems, 2022, 28(2): 103–125. doi: 10.1504/IJCNDS.2022.121195 [7] BOSE T, SURESH A, PANDEY O J, et al. Improving quality-of-service in cluster-based UAV-assisted edge networks[J]. IEEE Transactions on Network and Service Management, 2022, 19(2): 1903–1919. doi: 10.1109/TNSM.2021.3139892 [8] SHARMA M, KUMAR P, and TOMAR R S. Weight-based clustering algorithm for military vehicles communication in VANET[J]. SAIEE Africa Research Journal, 2023, 114(1): 25–34. doi: 10.23919/SAIEE.2023.9962790 [9] FROST P, MCCLUNG C, and WALLS C. Tactical considerations for a commander to fight and win in the electromagnetic spectrum[J]. The Cyber Defense Review, 2018, 3(1): 15–26. [10] LI Jiaxun, ZHAO Haitao, WEI Jibo, et al. Sender-jump receiver-wait: A simple blind rendezvous algorithm for distributed cognitive radio networks[J]. IEEE Transactions on Mobile Computing, 2018, 17(1): 183–196. doi: 10.1109/TMC.2017.2703166 [11] LI Jiaxun, ZHAO Haitao, HAFID A S, et al. A bio-inspired solution to cluster-based distributed spectrum allocation in high-density cognitive Internet of Things[J]. IEEE Internet of Things Journal, 2019, 6(6): 9294–9307. doi: 10.1109/JIOT.2019.2911542 [12] STEPHAN T, AL-TURJMAN F, JOSEPH K S, et al. Artificial intelligence inspired energy and spectrum aware cluster based routing protocol for cognitive radio sensor networks[J]. Journal of Parallel and Distributed Computing, 2020, 142: 90–105. doi: 10.1016/j.jpdc.2020.04.007 [13] 刘琰, 赵海涛, 李卫, 等. 一种基于邻域信息的多信道自适应建网算法[J]. 信号处理, 2022, 38(11): 2372–2384. doi: 10.16798/j.issn.1003-0530.2022.11.014LIU Yan, ZHAO Haitao, LI Wei, et al. Multi-channel adaptive network establishment based on neighborhood information[J]. Journal of Signal Processing, 2022, 38(11): 2372–2384. doi: 10.16798/j.issn.1003-0530.2022.11.014 [14] SAMAD A, QADIR M, and NAWAZ I. SAM: A similarity measure for link prediction in social network[C]. 2019 13th International Conference on Mathematics, Actuarial Science, Computer Science and Statistics (MACS), Karachi, Pakistan, 2019: 1–9. doi: 10.1109/MACS48846.2019.9024762. [15] NEWMAN M E J and GIRVAN M. Finding and evaluating community structure in networks[J]. Physical Review E, 2004, 69(2): 026113. doi: 10.1103/PhysRevE.69.026113 [16] BLONDEL V D, GUILLAUME J L, LAMBIOTTE R, et al. Fast unfolding of communities in large networks[J]. Journal of Statistical Mechanics:Theory and Experiment, 2008, 2008: P10008. doi: 10.1088/1742-5468/2008/10/P10008 [17] LIANG Xinyu, LIANG Jiarong, and ZHANG Weiguang. Constructing d-robust connected dominating sets in wireless sensor networks with unstable transmission ranges[J]. IEEE Transactions on Communications, 2021, 69(1): 398–415. doi: 10.1109/TCOMM.2020.3030930 -
下载:
图(8) / 表(3)
计量
- 文章访问数: 147
- HTML全文浏览量: 117
- PDF下载量: 40
- 被引次数: 0
