ISSN1004-9037,CODEN SCYCE4
Journal of Data Acquisition and Processing Vol.36,No.2,Mar.2021,pp.280-288 DOI：10.16337/j.1004-9037.2021.02.009
©2021by Journal of Data Acquisition and Processing
sjcj.nuaa.edu
E-mail:sjcj@nuaa.edu Tel/Fax：十86-025-********
基于K-means和SOM的水下传感器数据采集方法
洪悅1郭承军2
(1.电子科技大学电子科学技术研究院，成都611731；2.电子科技大学通信抗干扰技术国家级重点实验室，成都611731)
摘要：随着海洋资源勘探和海洋污染物监控工作的开展，水文数据的监测和采集等已经成为重要的研究方向。其中，水下无线传感器网络在水文数据采集过程中起着举足轻重的作用。本文研究的是水下无线
传感器二维监测网络模型中，传感器节点数据采集的问题，其设计方法是通过自组织映射(Selforganizing mapping,SOM)对传感器节点进行路径最优化处理，结合优化的路径图形和K-means算法到路径内部聚合点，利用聚合点和传感器的节点得到传感器通信半径内的数据采集点，最后通过SOM 得到水下机器人(Autonomous underwater vehicle,AUV)到各个数据采集点采集数据的最优路径。经过实验验证，在水下1200m X1750m范围内布置52个传感器节点的情景下，数据采集点相比于传感器节点路径规划采用相同的采集顺序得到的路径优化了 6.7%；对数据采集点重新进行自组织路径规划得到的路径比传感器结点路径的最优解提高了12.2%。增加传感器节点的数量，其结果也大致相同，因此采用该方法可以提高水下机器人采集数据的效率。
关键词：K-means算法；自组织神经网络；无线传感器网络；路径规划；数据采集
中图分类号：TP317文献标志码:A
Data Collection Method of Underwater Sensor Based on K-means and SOM
HONG Yue1，GUO Chengjun2
(1.Institute of Electronic Science and Technology,University of Electronic Science and Technology,Chengdu611731,China；
2.State Key Laboratory of Communication Anti-interference Technology,University of Electronic Science and Technology, Chengdu611731,China)
Abstract：With the development of marine resource exploration and marine pollutant monitoring，monitoring and collection of hydrologic data have become an important research direction.Among them，underwater wireless sensor networks play an important role in hydrological data acquisition.This paper studies the data collection of sensor nodes in the two-dimensional monitoring model network of underwater wireless sensors.The proposed method optimizes the path of sensor nodes by using self-organizing mapping(SOM).We combine the optimized path graphics and the K-means algorithm to find the path internal aggregation point.Then we find the data acquisition point within the sensor communication radius through the aggregation point and the sensor node.Finally，the optimal path of autonomaous underwater vehicle(AUV)to each data collection point is found through SOM.In the verification experiment，52 sensor nodes are arranged within a range of1200m X1750m under the water，and the path obtained by data collection points is optimized by6.7%compared with the path planning of sensor nodes in the same
收稿日期:2020-07-06；修订日期:2020-10-20
洪悦等：基于K-means和SOM的水下传感器数据采集方法281
acquisition sequence.Compared with the optimal solution of sensor node path,the path obtained by reorganizing the self-organizing path planning of data collection points is improved by12.2%.The results of increasing the number of sensor nodes are similar,so the proposed method can improve the data acquisition efficiency of AUV.
Key words:K-means algorithm;self-organization neural networks;wireless sensor network;path programming;data collection
引言
随着海洋资源勘探和污染物监测工作的开展，各种关于海洋水文数据的采集技术不断发展成熟。其中水下无线传感器网络(Underwater sensor networks,UWSNs)就是对海洋信息采集的重要技术之一。水下无线传感器网络可以根据具体应用不同，分为多种系统结构。例如，根据监测的空间区域不同大致可分为二维、三维和海洋立体监测网络3种。本文研究的是应用于深海环境的二维监测网络结构。在该模型中，传感器节点被锚定在海底，采集到的信息通过水下机器人(Autonomous underwater vehicle，AUV)定时收集，最终将采集到的海底信息实时地传送给地面系统[13]o
传感器节点数据传输方式有多种，水生通讯就是其一。相比于水下电磁波在水中的衰减比较严重，不适合非接触式信号传输而言，水声非接触式信号传输是一个很好的选择。中科院沈阳自动化研究所研
制的“探索者”号无缆自治水下机器人的信息系统，实现水声通讯完成水上水下信息交换⑷。由于在近海及海面有噪声干扰，所以水声通讯更适合于深海环境。东北大学(美)Woods Hole海洋科学研究所在深海条件下，实现185.2km(100海里)的水声通讯，数据传输速率达到1Kb/s〔5〕。美国海军组建的实验性远程声纳和海洋网络计划的水声网络，通过海面的浮标将水下信息中转至陆空各种平台。由于在深海条件下，铺设电缆是比较大的工程，而非接触式通讯的通讯距离有限。在AUV技术不断成熟的条件下，使用AUV对深海条件下声传播传感器实现定时数据收集是一个比较好的选择，而在使用AUV对传感器节点进行数据采集的方法中，不得不考虑路径规划问题。2014年，Basagni等提岀了一种贪婪的自适应AUV路径规划算法⑷，该算法实现了传输数据的信息量最大化。2012年，Ho l linger等⑺提出了用改进的TSP算法遍历最大独立集的方法收集数据。伊君⑷提出了基于K-means的水下传感器网络AUV数据收集方法，通过K-means划分多个网络子集的方法产生最优路径。本文是在针对水下传感器节点稀疏情况下,AUV既可以遍历节点又可以根据传感器传播特点尽可能地优化路径。传感器节点在实现各种网络协议和应用系统时，存在以下一些现实约束⑷：传感器节点体积限制着电池能量；无线通信的能量消耗与通信距离的关系为E=Kd n，即距离d的增加会增加传感器节点的能耗，基于此，一般传感器节点的通信半径设置在100m以内；最后，高存储能力和高处理能力意味着高价格。
由于通信半径的限制，本文将通信半径p设置为100m。采集点设置为通信半径p覆盖区域内距离节点90m的点位；AUV到达数据采集点进行数据采集。
AUV采集数据也是旅行商(Travelling salesman problem,TSP)问题。自组织映射网络(Self-orga-nizing map,SOM)方法是解决TSP问题的方法之一。和传统的聚类方法相比，SOM网络能够映射到一个曲面或平面上，从而保持拓扑结构不变。SOM与Hopfield神经网络〔10〕算法比较，优势在于其避免了陷入局部最小值现象，具有更快的速度和更高的精度。
本文最主要的是解决传感器节点的数据采集点的确定问题，只有确定采集点位置，才能用TSP进行路径规划。采集点的确立一方面是因为AUV无法真正到达传感器节点，另一方面确立合适的采集点可以缩短路径长度，提高效率。本文采用K-means算法协助确立合适的采集点。
282数据采集与处理 Journal of Data A cquisitio n and Processing Vol. 36 , No. 2, 20211 SOM 解决路径规划算法
SOM 路径规划算法的主要原理是每次到离节点最近的神经元，该神经元被称为优胜神经元，然 后以该神经元建立一个高斯分布逐渐更新其他神经元的位置，也就是更新输出神经元权值向量，通过 不断的迭代，输岀神经元会逐渐学习到输入数据背后的模式。在TSP 问题中二维传感器坐标或者采集 点坐标就是输入数据，传感器或者采集点空间位置就是网络需要学习的模式，在迭代的过程中，为了保 证算法的收敛，会更新学习率等参数，最终达到神经元不断地靠近节点的目的，最终输出一条最短遍历 节点回路⑴13]o
当将SOM 应用于TSP 时，输入层中的每个节点都表示一个传感器节点或者采集点节点，并用笛卡 尔坐标(C ”，C J 表示其位置。输出层神经元的权值与输出层神经元在同一个维度，表示神经元的位置。 由于TSP 的基本要求是访问所有节点并最终返回起点，因此输出层使用了一个圆形拓扑。在形成这样 的拓扑结构之后，神经元在整个训练过程中竞争成为赢家，这一过程采用了由两个不同的过程组成的 无监督策略。输入的第q 个节点的向量表示形式为
C = ( c ”)T (1)
与第j 个输出节点相关联的权重的向量表示形式为W ,=( W j ” W jy )
(2)SOM 算法如下：
(1) 初始化输出层各个节点的权值W ji E (0, 1)，i = x,y ，j = 1,2,…，n 。同时指定学习速率a (t ) 的值和邻域函数f (d ,G ), t 为迭代次数，丁为总学习次数。邻域函数表示在步骤(5)中确定的获胜神经 元的邻域。
(2) 随机选取一个样本数据提供给输入层，并进行标准化处理。标准化处理目的在于方便步骤(4) 中计算欧氏距离以确定获胜神经元。
C q =丄=(c q ,)T
数据收集||C 1 [(cq)2( c q )2 卡(3) 对输出层的权重进行标准化处理。这里同样是为了计算欧氏距离。
W ，= W j = (W )T
j = Il W j ll = “ ,2 ,、洛[(W jq ) ,( W jy ) ]2(4) 计算输入样本点C q '和所有输出层节点W j '之间的欧氏距离。
丄
d j = ||C q ，— W j ‘II = [(— w jq )2 + (c y — w jq )2]2
(5) 从步骤(4)计算得到的欧氏距离中，岀最小的距离d 「，即为获胜神经元。d c = min [ d j ] j =1,2, 3, •••,〃？
(6) 为了向目标节点靠近，对获胜神经元及其邻域内神经元的权值进行重新计算，而不在邻域内的
神经元，则保持不变。W j (t + 1)= W j (t )+ a (t )f (d , G )•[ C q - W j (t )]
(7)(7) 不断重复步骤(4~6)直到到达目标迭代次数或者学习率到达阈值为止。在SOM 学习过程中，学习速率a (t )决定学习时间，若学习速率a (t )设定过大，这里指接近1，则会 导致权重的更新幅度过大而
产生振荡，这会造成学习的不稳定性。相反若把学习速率a (t )设定过小， 这里指趋于0，则会造成权重更新幅度过小，从而使收敛时间过长。在学习过程中动态地调整学习率可 以解决这一问题。学习速率公式为
( 3)
( 4)
( 5)
( 6)
洪 悦 等：基于K-means 和SOM 的水下传感器数据采集方法283
Q ( t )= &0(1— T )
(8)式中卫0为初始设定的学习率卫(t )为t 时刻的学习率，&( t )e (0,1)；；为迭代次数；t 为指定的迭代总次 数。此外，邻域函数/ (d,G )也可以同学习率一样设置为动态的可调整状态。动态设定邻域值，不仅可以加速学习过程，又可以保证学习的必然收敛，并且可以降低 造成网络扭曲的可能性[14-19]o 可以用多种形式设定该函数。 本文设置邻域函数为
f (d,G )=e —d 2/G2 (9)
式中：G 为时间的单调递减函数，d 为邻域神经元和获胜神经 元的坐标距离。
本文采用的是已经公布的TSP 数据集，首先以 1200m X 1 750 m 内52个传感器的节点进行实验，经过 SOM 的路径规划可以得到优化的路径规划图。通过SOM 规划的路径长度为11=7 874.59 m (最优值为l Q =7 542 m ), 如图1所示。Fig.1 SOM path planning diagram of sen sor node 2 K-means 算法得到采集点位置
K-means 算法是一种通过迭代求解的聚类分析算法⑵-21】。K-means 算法中的K 代表类簇个数， Means 代表类簇内数据对象的均值。K-means 算法以欧式距离作为数据对象间相似性度量的标准，即 数据对象间的距离越小，则它们的相似性越高，它们越有可能在同一个类簇。
K-means 算法具体实现步骤为：先根据数据的先验知识选择一个合适的K 值，然后选择K 个初 始的质
心。由于K-means 算法是启发式算法，K 个初始化的质心位置选择对最后的聚类结果和运行 时间都有很大影响。本文根据之前基于SOM 算法对传感器节点路径规划图形的分析，拟采用4个 聚类中心，即K =4o K-means 算法首先对数据进行预处理，将数据按比例放置在1X 1的二维坐标内
c ,min, C 儿 min = min C ( q , c j
(10)C , max , C 儿 max = max C ( 0,0)
(11)C x =( C x C x _ min )/( C x _ max C x _ min )
( 12 )5 =( C j — C y _mm )/( C y _ max — C y _ min ) (13)
因此可将4个初始类簇中心设置为(0.75,0.75),0.25,0.75),0.25,0.25), (0.75,0.25)；接着根据 欧式距离划分所属类簇中心，欧式距离计算公式为
Center k 14)
15)dist( C i , C j )= (. — C jx )2 +(c i y — c jy )2然后根据所属类簇中心K 的点对类簇中心的坐标进行重新计算
S C
i M k C i e M k
式中：为第k 个类簇中心, M k |为第k 个类簇中心的数据个数。接着再重新划分所属类簇中心的点, 并重新计算类簇中心的坐标，不断迭代，直到所属类簇中心的点不再变化为止；最后再将类簇中心和所 有的点按比例还原到原来的坐标，如图2所示。
五角星表示4个类簇质心，其他包括点、三角形、正方形和叉等形状的坐标分别代表所属4
个类簇
284数据采集与处理 Journal of D ata Acquisition and Processing Vol. 36, No. 2, 2021中心的传感器点，且每个类簇中心都被所属传感器节点包围。将形成的4个类簇中心放进传感器节点 规划的路径中，如图3所示。
1200
1 000
800
600
400
200
0 250 500 750 1 000 1 2501 500 1 750
x / m
图2 K -means 算法传感器节点类簇中心Fig.2 K -means algorithm sensor node class cluster cen 图3 K -means 算法聚类中心在规划路径中Fig.3 K -means algorithm clustering center in the plan
ning path ter 从图3可以看出4个聚类中心都在规划路径的内部，右上侧的类簇中心较靠近路径边界，从图2可 以分析出该类簇中心的点位只有4个，数量较少且坐标差异较大，因此不能将类簇中心理想地放置在规 划路径的内部较中心的位置，但对结果影响不大。
K-means 算法原理比较简单，实现也很容易，收敛速度快。虽然算法的最初需要根据经验设置K 值 和初始类簇中心，但是聚类效果较优，符合本文的要求。3算法流程
根据前文的介绍，首先根据传感器节点通过SOM 对路径进行规划；然后根据规划出的路径进行图 形分析，确定K-means 算法初始类簇中心和K 值，通过K-means 算法计算出最终的类簇中心；其次根据 式（16）确定采集点位置。
叫U ky — C y
U kx — C x (叫—C x )+ C y (16)— C x )2 + (m y — C y )2 = 90
式中：U （U kx,U ky ）为第k 个类簇中心,C （C x ，C y ）为属于第k 个类簇中心的传感器节点,M （m x ，m y ）为采集 点。最后，对采集点进行路径规划，分为两次，第一次是引用传感器节点路径规划连接方式得到路径， 第二次对采集点重新进行SOM 路径规划得到路径。具体算法流程如下：
（1） 输入n 个二维传感器节点（C 】，C 2,…，C n ），第q 个节点坐标表示为C （C q ，）。（2）
使用SOM 对输入传感器节点进行路径规划，且得到路径连接序列，0=0.8，神经元个 数为8n 。
（3）将传感器节点按比例缩放至1X 1的坐标系内，对图形进行分析，确定初始类簇中心U 0以及K 的值。
（4） 使用K-means 算法进行类簇中心计算，重新得到U （u*，y ），=1,2，…，K 。（5） 将传感器节点和类簇中心代入式（16）计算得到n 个采集点（M 】,M S …,M n ），将采集点坐标 还原
（6） 对采集点按照步骤（1,2）得到的序列连接，得到路径规划图（7） 对采集点按照步骤（1,2）SOM 重新进行路径规划。
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论