User cluster partitioning method based on weighted fuzzy clustering in ground-air collaboration scenarios

doi:10.11772/j.issn.1001-9081.2023050643

Journal of Computer Applications ›› 2024, Vol. 44 ›› Issue (5): 1555-1561.DOI: 10.11772/j.issn.1001-9081.2023050643

Special Issue: 网络与通信

• Network and communications • Previous Articles Next Articles

User cluster partitioning method based on weighted fuzzy clustering in ground-air collaboration scenarios

Tianyu HUANG¹^,², Yuanxing LI¹, Hao CHEN¹(), Zijia GUO¹, Mingjun WEI¹^,²

^1.College of Artificial Intelligence，North China University of Science and Technology，Tangshan Hebei 063210，China
^2.Hebei Key Laboratory of Industrial Intelligent Perception，Tangshan Hebei 063210，China

Received:2023-05-24 Revised:2023-08-21 Accepted:2023-08-25 Online:2023-08-28 Published:2024-05-10
Contact: Hao CHEN
About author:HUANG Tianyu， born in 1983， Ph. D.， lecturer. His research interests include UAV-assisted communication， blockchain.
LI Yuanxing， born in 1998， M. S. candidate. His research interests include UAV-assisted communication， UAV base station deployment strategy， fuzzy clustering.
GUO Zijia， born in 1996， M. S. candidate. Her research interests include blockchain， computing resource.
WEI Mingjun， born in 1969， M. S.， professor. His research interests include computer vision， intrusion detection， machine learning， data mining.

地空协同场景下加权模糊聚类用户簇划分方法

黄天宇¹^,², 李远兴¹, 陈昊¹(), 郭紫佳¹, 魏明军¹^,²

^1.华北理工大学人工智能学院，河北唐山 063210
^2.河北省工业智能感知重点实验室，河北唐山 063210

通讯作者: 陈昊
作者简介:黄天宇（1983—），男，河北唐山人，讲师，博士，主要研究方向：无人机辅助通信、区块链
李远兴（1998—），男，山东泰安人，硕士研究生，主要研究方向：无人机辅助通信、无人机基站部署策略、模糊聚类
郭紫佳（1996—），女，河北石家庄人，硕士研究生，主要研究方向：区块链、计算资源
魏明军（1969—），男，河北唐山人，教授，硕士，主要研究方向：计算机视觉、入侵检测、机器学习、数据挖掘。
第一联系人：陈昊（1976—），男，河北唐山人，副教授，博士，主要研究方向：人工智能

Abstract

Abstract:

To address the user cluster partitioning issue in the deployment strategy of Unmanned Aerial Vehicle （UAV） base stations for auxiliary communication in emergency scenarios， a feature-weighted fuzzy clustering algorithm， named Improved FCM， was proposed by considering both the performance of UAV base stations and user experience. Firstly， to tackle the problem of high computational complexity and convergence difficulty in the partitioning process of user clusters under random distribution conditions， a feature-weighted node data projection algorithm based on distance weighting was introduced according to the performance constraints of signal coverage range and maximum number of served users for each UAV base station. Secondly， to address the effectiveness of user partitioning when the same user falls within the effective ranges of multiple clusters， as well as the maximization of UAV base station resource utilization， a value-weighted algorithm based on user location and UAV base station load balancing was proposed. Experimental results demonstrate that the proposed methods meet the service performance constraints of UAV base stations. Additionally， the deployment scheme based on the proposed methods effectively improves the average load rate and coverage ratio of the system， reaching 0.774 and 0.026 3 respectively， which are higher than those of GFA （Geometric Fractal Analysis）， Sp-C （Spectral Clustering）， etc.

Key words: ground-air collaboration, emergency communication, Unmanned Aerial Vehicle (UAV)-assisted communication, Unmanned Aerial Vehicle (UAV) base station deployment, user cluster partitioning, feature weighting, Fuzzy C-means Clustering (FCM)

摘要：

为了解决应急通信场景下使用无人机作为空中基站进行辅助通信时涉及的无人机基站部署策略中的用户簇划分问题，在兼顾无人机基站性能和用户体验的条件下，提出一种基于特征加权的模糊聚类（Improved FCM）算法。首先，根据每个无人机基站的信号覆盖范围和最大服务用户数量的性能约束，针对随机分布条件下的用户簇在划分过程中算法计算量大不易收敛的问题，提出一种基于距离加权的特征加权节点数据投影算法；其次，针对同一用户处于多个簇有效范围内时用户划分的有效性和无人机基站资源的最大化利用问题，提出一种基于用户位置和无人机基站负载均衡的价值加权算法。实验结果表明，所提方法充分满足无人机基站的服务性能约束，且与几何分形法（GFA）、谱聚类（Sp-C）等算法相比，特征加权模糊聚类算法获得的平均负载率和覆盖比是最优的，分别达到了0.774和0.026 3，因此，该算法可为应急通信场景下的用户簇划分问题提供一种可行的解决方案。

关键词: 地空协同, 应急通信, 无人机辅助通信, 无人机基站部署, 用户簇划分, 特征加权, 模糊C均值聚类

CLC Number:

TP391

Tianyu HUANG, Yuanxing LI, Hao CHEN, Zijia GUO, Mingjun WEI. User cluster partitioning method based on weighted fuzzy clustering in ground-air collaboration scenarios[J]. Journal of Computer Applications, 2024, 44(5): 1555-1561.

黄天宇, 李远兴, 陈昊, 郭紫佳, 魏明军. 地空协同场景下加权模糊聚类用户簇划分方法[J]. 《计算机应用》唯一官方网站, 2024, 44(5): 1555-1561.

Figures/Tables 9

Fig. 1 Multi-network planning model for UAV-assisted communication

Tab. 1 System parameter definition

参数	含义
$N u$	请求需求的基站数量
$N p$	请求区域内包含的用户数量
$N u m a x$	基站最大服务用户数量
$N u m i n$	基站最小服务用户数量
$R u m a x$	基站的最大覆盖半径
$d$	基站与用户之间的距离
$N u$	第 $u$ 个基站内包含的用户数量
$R o u t$	请求区域内的网络覆盖率
$B ˜$	区域内基站的平均负载率
$d c$	截断距离
$p c u$	第 $u$ 个类的价格指标
$W i u$	根据价格指标调整后的隶属值
$λ$	用户的分布密度

Tab. 1 System parameter definition

参数	含义
$N u$	请求需求的基站数量
$N p$	请求区域内包含的用户数量
$N u m a x$	基站最大服务用户数量
$N u m i n$	基站最小服务用户数量
$R u m a x$	基站的最大覆盖半径
$d$	基站与用户之间的距离
$N u$	第 $u$ 个基站内包含的用户数量
$R o u t$	请求区域内的网络覆盖率
$B ˜$	区域内基站的平均负载率
$d c$	截断距离
$p c u$	第 $u$ 个类的价格指标
$W i u$	根据价格指标调整后的隶属值
$λ$	用户的分布密度

Tab. 2 Simulation parameter setting

符号	数值	符号	数值
$λ$	0.5~2.5	$N u m a x$	100
$R u m a x$	2.5 km	$N u m i n$	50
$d c$	$R u m a x$	$l o r$	0.8

Tab. 2 Simulation parameter setting

符号	数值	符号	数值
$λ$	0.5~2.5	$N u m a x$	100
$R u m a x$	2.5 km	$N u m i n$	50
$d c$	$R u m a x$	$l o r$	0.8

Fig. 2 Original user location distribution

Fig. 3 Objective function curve

Fig. 4 Cluster partitioning results

Tab. 3 Comparison experiment parameter setting

符号	数值	符号	数值
$N p$	1 000	$N u m i n$	50
$L × H$	10 km ×10 km	$N u m a x$	100
$R u m a x$	2.5 km	$K$	13

Tab. 3 Comparison experiment parameter setting

符号	数值	符号	数值
$N p$	1 000	$N u m i n$	50
$L × H$	10 km ×10 km	$N u m a x$	100
$R u m a x$	2.5 km	$K$	13

Tab. 4 Average load rate comparison

算法	平均负载率	算法	平均负载率
Improved FCM	77.4	Sp-C	66.84
GFA	68.4	ISODATA	65.36

Tab. 5 Coverage ratio comparison

算法	覆盖比	算法	覆盖比
Improved FCM	2.63	Sp-C	2.27
GFA	2.33	ISODATA	2.22

References 31

1	KAZMI S H A， QAMAR F， HASSAN R， et al. Survey on joint paradigm of 5G and SDN emerging mobile technologies： architecture， security， challenges and research directions［J］. Wireless Personal Communications， 2023， 130： 2753-2800. 10.1007/s11277-023-10402-7
2	YEH C， DO JO G， Y-J KO， et al. Perspectives on 6G wireless communications［J］. ICT Express， 2023， 9（1）： 82-91. 10.1016/j.icte.2021.12.017
3	CHAFII M， BARIAH L， MUHAIDAT S， et al. Twelve scientific challenges for 6G： rethinking the foundations of communications theory［J］. IEEE Communications Surveys & Tutorials， 2023， 25（2）： 868-904. 10.1109/comst.2023.3243918
4	SHEN L-H， FENG K-T， HANZO L. Five facets of 6G： research challenges and opportunities［J］. ACM Computing Surveys， 2023， 55（11）： No 235. 10.1145/3571072
5	WANG Q， LI W， YU Z， et al. An overview of emergency communication networks［J］. Remote Sensing， 2023， 15（6）： 1595. 10.3390/rs15061595
6	DAW S， KAR A， TAMMA B R. On enhancing semi-persistent scheduling in 5G NR V2X to support emergency communication services in highly congested scenarios［C］// Proceedings of the 24th International Conference on Distributed Computing and Networking. New York： ACM， 2023： 245-253. 10.1145/3571306.3571409
7	DASH B， ANSARI M F， SWAYAMSIDDHA S. Fusion of artificial intelligence and 5G in defining future UAV technologies： a review［C］// Proceedings of the 2023 International Conference on Device Intelligence， Computing and Communication Technologies. Piscataway： IEEE， 2023： 312-316. 10.1109/dicct56244.2023.10110231
8	MAYOR V， ESTEPA R， ESTEPA A. CO-CAC： a new approach to call admission control for VoIP in 5G/WiFi UAV-based relay networks［J］. Computer Communications， 2023， 197： 284-293. 10.1016/j.comcom.2022.11.006
9	MENG K， WU Q， XU J， et al. UAV-enabled integrated sensing and communication： opportunities and challenges［EB/OL］. ［2023-05-01］. . 10.1109/mwc.131.2200442
10	LIU X， WANG X， HUANG M， et al. Deployment of UAV-BSs for on-demand full communication coverage［J］. Ad Hoc Networks， 2023， 140： 103047. 10.1016/j.adhoc.2022.103047
11	DANTRAKUL S， LIKASIRI C， PONGVUTHITHUM R. Applied p‑median and p-center algorithms for facility location problems［J］. Expert Systems with Applications， 2014， 41（8）： 3596-3604. 10.1016/j.eswa.2013.11.046
12	CHEN L， CHEN S-J， CHEN W-K， et al. Efficient presolving methods for solving maximal covering and partial set covering location problems［J］. European Journal of Operational Research， 2023， 311（1）： 73-87. 10.1016/j.ejor.2023.04.044
13	MA X Y， ZHANG X Y， ZHAO X. Service coverage optimization for facility location： considering line-of-sight coverage in continuous demand space［J］. International Journal of Geographical Information Science， 2023， 37（7）： 1496-1519. 10.1080/13658816.2023.2193829
14	BLANCO V， GÁZQUEZ R， SALDANHA-DA-GAMA F. Multi-type maximal covering location problems： hybridizing discrete and continuous problems［J］. European Journal of Operational Research， 2023， 307（3）： 1040-1054. 10.1016/j.ejor.2022.10.037
15	SHEN H， JIANG R. Chance-constrained set covering with Wasserstein ambiguity［J］. Mathematical Programming， 2023， 198（1）： 621-674. 10.1007/s10107-022-01788-6
16	BOR-YALINIZ R I， EL-KEYI A， YANIKOMEROGLU H. Efficient 3-D placement of an aerial base station in next generation cellular networks［C］// Proceedings of the 2016 IEEE International Conference on Communications. Piscataway： IEEE， 2016： 1-5. 10.1109/icc.2016.7510820
17	SHARMA V， SRINIVASAN K， CHAO H-C， et al. Intelligent deployment of UAVs in 5G heterogeneous communication environment for improved coverage［J］. Journal of Network and Computer Applications， 2017， 85： 94-105. 10.1016/j.jnca.2016.12.012
18	BOSCHIERO M， GIORDANI M， POLESE M， et al. Coverage analysis of UAVs in millimeter wave networks： a stochastic geometry approach［C］// Proceedings of the 2020 International Conference on Wireless Communications and Mobile Computing. Piscataway：IEEE， 2020： 351-357. 10.1109/iwcmc48107.2020.9148550
19	ZHANG S， LIU J， SUN W. Stochastic geometric analysis of multiple unmanned aerial vehicle-assisted communications over Internet of Things［J］. IEEE Internet of Things Journal， 2019， 6（3）： 5446-5460. 10.1109/jiot.2019.2902162
20	MOZAFFARI M， SAAD W， BENNIS M， et al. Efficient deployment of multiple unmanned aerial vehicles for optimal wireless coverage［J］. IEEE Communications Letters， 2016， 20（8）： 1647-1650. 10.1109/lcomm.2016.2578312
21	SHUKLA S， THAKUR R， AGARWAL S. Particle swarm optimization algorithms for altitude and transmit power adjustments in UAV-assisted cellular networks［C］// Proceedings of the 2021 IEEE 93rd Vehicular Technology Conference. Piscataway：IEEE， 2021： 1-6. 10.1109/vtc2021-spring51267.2021.9448994
22	GUO H， LIU J. UAV-enhanced intelligent offloading for Internet of Things at the edge［J］. IEEE Transactions on Industrial Informatics， 2019， 16（4）： 2737-2746. 10.1109/tii.2019.2954944
23	ZENG Y， ZHANG R. Energy-efficient UAV communication with trajectory optimization［J］. IEEE Transactions on Wireless Communications， 2017， 16（6）： 3747-3760. 10.1109/twc.2017.2688328
24	ATAEI H， DAVOODI M. The p-center problem under locational uncertainty of demand points［J］. Discrete Optimization， 2023， 47： 100759. 10.1016/j.disopt.2023.100759
25	CHURCH R L， DREZNER Z， KALCZYNSKI P. Extensions to the planar p-median problem［J］. Annals of Operations Research， 2023， 326： 115-135. 10.1007/s10479-023-05279-5
26	WANG L， HU B， CHEN S. Energy efficient placement of a drone base station for minimum required transmit power［J］. IEEE Wireless Communications Letters， 2020， 9（12）： 2010-2014. 10.1109/lwc.2018.2808957
27	S-C NOH， H-B JEON， C-B CHAE. Energy-efficient deployment of multiple UAVs using ellipse clustering to establish base stations［J］. IEEE Wireless Communications Letters， 2020， 9（8）： 1155-1159. 10.1109/lwc.2020.2982889
28	CUI J， SHAKHATREH H， HU B， et al. Power-efficient deployment of a UAV for emergency indoor wireless coverage［J］. IEEE Access， 2018， 6： 73200-73209. 10.1109/access.2018.2882896
29	SAVKIN A V， HUANG H. Deployment of unmanned aerial vehicle base stations for optimal quality of coverage［J］. IEEE Wireless Communications Letters， 2019， 8（1）： 321-324. 10.1109/lwc.2018.2872547
30	SOBOUTI M J， RAHIMI Z， MOHAJERZADEH A H， et al. Efficient deployment of small cell base stations mounted on unmanned aerial vehicles for the internet of things infrastructure［J］. IEEE Sensors Journal， 2020， 20（13）： 7460-7471. 10.1109/jsen.2020.2973320
31	黄天宇. 无人机辅助通信中基站部署策略研究［D］. 秦皇岛：燕山大学， 2019.
	HUANG T Y. Research on UAV deployment in UAV aided communication［D］. Qinhuangdao： Yanshan University， 2019.

[1]	Yu YANG, Weiwei DUAN. Spectral clustering based dynamic community discovery algorithm in social network [J]. Journal of Computer Applications, 2023, 43(10): 3129-3135.
[2]	Gaofeng PAN, Yuan FAN, Yu RU, Yuchao GUO. Low-texture monocular visual simultaneous localization and mapping algorithm based on point-line feature fusion [J]. Journal of Computer Applications, 2022, 42(7): 2170-2176.
[3]	CAI Ruiguang, ZHANG Desheng, XIAO Yanting. Parameter independent weighted local mean-based pseudo nearest neighbor classification algorithm [J]. Journal of Computer Applications, 2021, 41(6): 1694-1700.
[4]	YUAN Qianqian, DENG Hongmin, WANG Xiaohang. Citrus disease and insect pest area segmentation based on superpixel fast fuzzy C-means clustering and support vector machine [J]. Journal of Computer Applications, 2021, 41(2): 563-570.
[5]	SUN Jianjun, XU Yan. Estimation of underdetermined mixing matrix based on improved weighted fuzzy C-means clustering [J]. Journal of Computer Applications, 2020, 40(6): 1769-1773.
[6]	ZHU Jie, ZHANG Junsan, WU Shufang, DONG Yukun, LYU Lin. Multi-center convolutional feature weighting based image retrieval [J]. Journal of Computer Applications, 2018, 38(10): 2778-2781.
[7]	QIU Yunfei, LIU Shixing, LIN Mingming, SHAO Liangshan. Feature transfer weighting algorithm based on distribution and term frequency-inverse class frequency [J]. Journal of Computer Applications, 2015, 35(6): 1643-1648.
[8]	ZHI Xiaobin, XU Zhaohui. Robust soft subspace clustering algorithm with feature weight self-adjustment mechanism [J]. Journal of Computer Applications, 2015, 35(3): 770-774.
[9]	CHEN Yongjian WANG Xili. Semi-supervised SVM image classification method with pre-selected sample by fuzzy C-mean [J]. Journal of Computer Applications, 2014, 34(1): 260-264.
[10]	ZHU Quan JIANG Xin-hua ZOU Fu-min XU Shao-feng. Improvement on multi-hop performance of underground mine emergency communication system based on WMN [J]. Journal of Computer Applications, 2012, 32(03): 800-803.
[11]	LIU Lei CHEN Xing-shu YIN Xue-yuan DUAN Yi LV Zhao. Network User Identify On Feature Weighting Naive Bayes Classification Algorithm [J]. Journal of Computer Applications, 2011, 31(12): 3268-3270.
[12]	. Chaotic spread spectrum-based model design and simulation of multi-user emergency communication system [J]. Journal of Computer Applications, 2011, 31(01): 235-238.
[13]	. Margin maximization feature weighting with better adaptability [J]. Journal of Computer Applications, 2010, 30(9): 2275-2278.

User cluster partitioning method based on weighted fuzzy clustering in ground-air collaboration scenarios

地空协同场景下加权模糊聚类用户簇划分方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 31

Related Articles 13

Recommended Articles

Metrics