A Path Planning Method for Water Surface Mobile Sink Based on Voronoi Diagram and Bipartite Graph
-
摘要: 水面传感器网络（Surface sensor networks，SSNs）具有节点稀疏布置的特点（节点间距离通常大于节点通信半径），因此难以通过节点间的多跳路由汇聚数据，目前主要采用移动基站（Mobile sink，MS）收集网络中的数据，其中移动基站的路径规划是一个关键问题.该文提出一种基于维诺图和二分图的水面移动基站路径规划方法，首先利用维诺图理论生成数据收集“候选点”；然后以二分图描述候选点对网络中传感器节点的支配关系，并基于支配集理论求解出“最小有效支配集”，即可以收集网络中所有节点数据的最小的候选点集合；最后针对最小有效支配集形成最优路径.大量实验结果表明该方法可以有效地规划出水面传感器网络中移动基站的路径，不仅可以完成全网数据收集任务，而且具有路径长度短、能量效率高和节点能耗均衡的优点.Abstract: In surface sensor networks with sparsely deployed sensors, the distance between sensors is usually larger than the communication radius of sensors. So, it is difficult for sensors to gather their data by multi-hop routing. At present, an effective data gathering method is to use a mobile sink travelling in the network, and the path planning for the mobile sink becomes a key problem. In this paper, a path planning method based on Voronoi diagram and bipartite graph is proposed. Firstly, the data gathering "candidate vertexes" are generated using the Voronoi diagram theory. Secondly, a bipartite graph is constructed to describe the dominating relationship between candidate vertexes and sensors, and the "minimum effective dominating set", which includes the least candidate vertexes gathering all sensors data, can be computed by dominating set theory. Lastly, the optimal path is formed based on the minimum effective dominating set. Extensive experiments have demonstrated that the proposed method can effectively plan the path for mobile sink to gather all sensors' data with advantages such as short path, high energy efficiency, and balanced energy consumption among sensors.
-
Key words:
- Surface sensor networks (SSNs) /
- mobile sink (MS) /
- path planning /
- Voronoi diagram /
- bipartite graph /
- dominating set
-
分类问题是机器学习的一个主要领域,其目标是通过对于给定数据集的学习,获得能够对未来数据进行有效分类的分类器 [1]. 基于不同的构造思路,已经有很多分类学习方法得到了深入的研究和广泛的应用,如贝叶斯方法、决策树方法、神经网络等.其中,支持向量机(Support vector machine,SVM) [2] 作为其中比较好的分类方法,得到了广泛的关注和应用. SVM将数据空间的数据通过映射到高维的特征空间,并在特征空间里面利用超平面作为决策平面,因此具有了稀疏性、效率高、准确性高等特点 [1-3].
最小二乘支持向量机(Least squares support vector machine,LS-SVM) [4]作为SVM的一种主要变形,通过将SVM中的罚函数替换为二次函数并将约 束条件转化为等式约束,使得LS-SVM的解可以通过求解一个线性系统来得到,简化了求解过程.实验表明,LS-SVM在实际应用中具有和SVM相类似的泛化能力,因此在很多领域取得广泛的应用 [5]. 但是,随着训练集数据量的增加,LS-SVM的弱点也越来越突出地表现出来.由于LS-SVM的支持向量几乎包含了全 部训练集的数据,随着数据量的增加,计算用时也会大量增加,从而限制了LS-SVM的进一步应用.因此,对LS-SVM进行支持向量数量的消减,继续保持SVMs的稀疏性特征,是LS-SVM适应新的要求必须要研究的问题 [6-8].
在LS-SVM稀疏化的研究中,基于迭代过程形成稀疏LS-SVM的支持向量集是目前研究的主要思路,可以分为删除式稀疏化方法和增量式稀疏化方法. 2000年,Suykens 等 [6]首先利用删除式稀疏化方法对LS-SVM进行稀疏化.在稀疏化过程中,每一步将支持向量集中最靠近当前决策超平面的若干个支持向量进行消减. 但是由于每次都要根据当前支持向量集进行求解线性系统,因此,在数据量较大的时候,其计算复杂性会非常高.随后,Suykens等 [7]在支持向量的选择中不仅考虑了LS-SVM模型的最优化,同时考虑了泛化能力. 在文献 [8]中,选择被消减支持向量的准则变为寻找并消减具有最小偏差的点,进一步提高了消减后的准确性. Hoegaerts等 [9]在文献[6]的基础上提出了一种轻量级变种稀疏化算法并改进了原算法的性能. 文献 [10] 在序列最小优化求解LS-SVM算法基础上,在每一步迭代中,将影响对偶目标函数值最小的数据点进行消减,从而达到稀疏化的目标. Carvalho等 [11]给出了一个两阶段消减算法,在已知LS-SVM决策超平面的前提下,利用碎片化指标度量每个支持向量的可消减性,进而进行稀疏化. de Brabanter等 [12]使用基于熵核频带宽度选择策略和快速交叉验证方法,对LS-SVM进行消减. Kars-makers等 [13]利用过决定线性系统的稀疏共轭方向寻踪稀疏化方法来对LS-SVM进行支持向量集的消减并取得了良好的效果. Lopez等 [14]在文献 [15]对 $L_0$ 范式进行迭代优化的基础上,将分类LS-SVM和回归LS-SVM都统一在一个稀疏化算法中. Liu等 [16]和Wei等 [17]在引入适应性Lp LS-SVM的基础上,用进化算法对其求解以实现LS-SVM的稀疏化.增量式稀疏化LS-SVM的研究也出现了许多成果. Jiao等 [18]在建立基于核的支持向量词典基础上,每次都将一个基本支持向量加入到支持向量集合中,在控制计算复杂度的前提下取得了良好的效果. Zhao等 [19]在假设后增加支持向量不影响当前支持向量的前提下,构造了一个增量式LS-SVM稀疏化算法,从空集开始,每一次都将剩余数据点中使得目标函数增长最少的点作为支持向量加入支持向量集中. Yang等 [20]利用迭代方法,在尽量保持信息不损失的情况下,交替使用增加和减少支持向量数量的方法,达到对LS-SVM的稀疏化的目标. Zhao等 [21]在文献[19]的基础上考虑到支持向量集变化对非支持向量的影响,通过重新计算剩余数据点对目标函数下降的贡献,选择其中使得目标函数下降最大的数据点进入支持向量集.除了传统稀疏化方法以外,数据压缩传感理论也被应用到了LS-SVM 的稀疏化上. Yang等 [22]提出了使用正交匹配追踪算法对训练数据集进行压缩,从而实现LS-SVM 的稀疏化. Yang等 [23]在上述研究的基础上,用非随机矩阵代替原有的随机高斯矩阵,进一步提高了算法的效率.从目前的研究来看,基于迭代的算法依然是主要研究的方向,但是存在计算复杂性较高,在数据量大的时候,其表现不能满足实际要求的情况.综上所述,LS-SVM的稀疏化是从原来几乎包含所有训练数据点的支持向量集中选择若干数据点,并通过计算使得基于选择数据点的决策超平面具有类似于未稀疏化LS-SVM的泛化能力. 因此,LS-SVM的稀疏化可以看作是数据点抽取并求解近似决策超平面的过程.基于数据 点抽取的思路,在本文中我们给出了一种非迭代的LS-SVM稀疏化方法.
在本文中,我们首先给出了基于支持向量数量约束的LS-SVM稀疏化优化模型.在此基础上,提出基于数据特征空间全局代表性的支持向量集非迭代选择策略,并提出了基于全局代表点的LS-SVM稀疏化算法(Global-representation-based sparse least squares support vector machine,GRS-LSSVM).该算法的主要思路是,首先计算特征空间中数据点之间的距离,在此基础上计算每个数据点的全局代表性,然后按照给定的稀疏化后LS-SVM支持向量集的数量约束,一次性选择最具代表性的数据点并构成稀疏化后的支持向量集,最后在该支持向量集的基础上,求得稀疏化后的LS-SVM的决策超平面.实验表明,GRS-LSSVM具有稀疏度高、稳定性好、计算复杂度低等优点.
本文下文组织如下:首先,对LS-SVM的相关模型进行回顾和总结;其次,给出基于全局代表性的稀疏化算法;然后,给出相关算法的实验结果,并对结果进行分析;最后,对本文加以总结,并进一步提出工作的方向.
1. LS-SVM 模型
LS-SVM是在SVM的基础上通过改变其罚函数而得到的.简单起见,设 $({ x},y)$ , $x \in {R^d}$ 为给定的一个数据及其标号或者函数值,如果是标号,对应的就是分类问题,如果是函数值,对应的就是回归问题. N个已知数据形成的集合 $X=\{{ x}_i\}$ 和 $Y=\{y_i\}$ 共同构成了训练集. SVM的目标是通过对训练集的学习,获得如下形式的决策超平面:
$f( x):\quad { \omega}^{\rm T}\cdot\phi({ x})+b=0 $
(1) 其中, $\phi (\cdot)$ 是从Rd到特征空间$H$的映射函数,ω是特征空间中的一个向量,b是一个实数. LS-SVM通过求解如下优化模型得到决策超平面:
$\matrix{ {\mathop {\min }\limits_{\omega ,b,e} {\rm{ }}J = {1 \over 2}{{\left\| \omega \right\|}^2} + {C \over 2}\sum\limits_{i = 1}^N {e_i^2} } \hfill \cr {s.t.{\omega ^{\rm{T}}} \cdot \phi ({x_i}) + b = {y_i} - {e_i},i = 1, \cdots ,N} \hfill \cr } $
(2) 其中,C是惩罚参数.
通过构造式(2)所对应的拉格朗日函数,并根据KKT (Karush-Kuhn-Tucker)条件,可得下式:
$\omega = \mathop \sum \limits_{i = 1}^N {\alpha _i}\phi ({x_i})$
(3) $\left[ {\matrix{ {K\left( {X,Y} \right)} & {\overline 1 } \cr {{{\overline 1 }^T}} & 0 \cr } } \right]\left[ \matrix{ \alpha \hfill \cr b \hfill \cr} \right] = \left[ \matrix{ Y \hfill \cr 0 \hfill \cr} \right]$
(4) 其中 $K(\Omega ,\Lambda ) = {[k({x_i},{x_j})]_{|\Omega | \times |\Lambda |}},{x_i} \in \Omega ,{x_j} \in \Lambda ,k( \cdot , \cdot )$ 是预先确定的核函数,1=(1,…,1)N×1,I是N阶单位矩阵.
由式(4)可以看出,决策超平面的系数通过求解线性系统获得,并且,求得的决策超平面是式(2)的最优解.因此,相对于SVM,LS-SVM的求解比较简单.但是,由于几乎全部αi都不为零,LS-SVM也失去了SVMs的稀疏性.在实际应用中,LS-SVM的非稀疏性妨碍了其进一步的应用和推广.因此,对LS-SVM进行稀疏化是扩展LS-SVM应用的必然选择.
2. 基于全局代表性的 LS-SVM稀疏化算法
LS-SVM稀疏化是在尽可能保持LS-SVM原有泛化能力的前提下,将大量支持向量进行消减的过程.在本节讨论基于全局代表性的非迭代稀疏化算法.
2.1 LS-SVM 稀疏化模型
LS-SVM稀疏化的目标就是用如下函数g(x)代替f(x)并尽量保持原有决策超平面的性质:
$g({ x}): \overline{{ \omega}}^{\rm T}\cdot\phi({ x})+b=y $
(5) 其中 $\overline{{ \omega}}=\sum_{i=1}^L\beta_i\phi({ s}_i)$ ,${s_i} \in X,L < N$ ,L是稀疏化后支持向量的个数.
令 $S=\{{ s}_1,\cdots,{ s}_L\}$ 为稀疏化后LS-SVM的支持向量集.由于通过式(4)求解的决策超平面f(x)是式(2)的最优解.因此,在给定稀疏化后支持向量个数L的前提下,用g(x)代替f(x)进行LS-SVM稀疏化的优化模型为如下形式:
$\eqalign{ & \mathop {\min }\limits_S \quad {J_g} - {J_f} \cr & s.t.|S| \le L,\quad S \subset X \cr} $
(6) 其中,Jf与Jg分别表示用f(x)与g(x)作为决策超平面时的J函数值.
由于Jf为一定值,因此,式(6)等价于如下模型:
$\begin{align} & {{\min }_{S}}\quad {{J}_{g}} \\ & s.t.\quad |S|\le L,\quad S\subset X \\ \end{align}$
(7) 其中,目标函数经过整理并省略常数部分后可得如下形式:
$\eqalign{ & {J_g} = {1 \over 2}{\left\| {\bar \omega } \right\|^2} + {C \over 2}\sum\limits_{i = 1}^N {{{({y_i} - {{\bar \omega }^{\rm{T}}} \cdot \phi ({x_i}) - b)}^2}} = \cr & {1 \over 2}({\beta ^{\rm{T}}}K(S,S)\beta ) + \cr & {C \over 2}\sum\limits_{i = 1} N ({\mu ^{\rm{T}}}\left[ \matrix{ K(S,{x_i})K({x_i},S){\rm{ }}K(S,{x_i}) \hfill \cr K({x_i},S){\rm{ 1}} \hfill \cr} \right]\mu - \left[ {2{y_i}K({x_i},S{\rm{ }}2{y_i})} \right]\mu ) = \cr & {1 \over 2}{\mu ^{\rm{T}}}A\mu - B\mu \cr} $
(8) 其中
$A = \left[ {\matrix{ {K(S,S)(1 + C\sum\limits_{i = 1}^N k ({x_i},{x_i})} & {C\sum\limits_{i = 1}^N K (S,{x_i})} \cr {C\sum\limits_{i = 1}^N K ({x_i},S)} & {CN} \cr } } \right]$
(9) $B=\left[ \begin{align} & C\sum\limits_{i=1}^{N}{{{y}_{i}}}K(S,{{x}_{i}}) \\ & \sum\limits_{i=1}^{N}{C{{y}_{i}}} \\ \end{align} \right]$
(10) $\mu =\left[ \begin{matrix} \begin{align} & \beta \\ & b \\ \end{align} \\ \end{matrix} \right]$
(11) 当S确定时,式(7)在如下情况下达到最小值:
$\mu ={{A}^{-1}}B$
(12) 由上面的讨论可知,对于任意给定的一组向量S,只要S使得式(9)满秩,则存在唯一的一组系数值为式(8)的最优解.因此,选择S集合是LS-SVM进行稀疏化的根本问题.
2.2 基于全局代表性的 S 集选取
由于从X中选取S集的问题是一个组合优化问题,很难找到全局最优解. 因此,当给定L的前提下,我们希望通过对LS-SVM特征进行分析,得到一种快速S集合选取方法.为了方便讨论,我们首先给出密度和离散度的定义.
由于在特征空间中,任意两点间的距离可以通过下式进行计算:
$d({{x}_{1}},{{x}_{2}})=\sqrt{k({{x}_{1}},{{x}_{1}})+k({{x}_{2}},{{x}_{2}})-2k({{x}_{1}},{{x}_{2}})}$
(13) 数据点x的密度大小可以用数据点特定邻域内点的个数来进行衡量.
定义 1 (数据密度). 特征空间中任一点x在θ邻域内的密度ρ定义为:
$\rho =\sum\limits_{j=1}^{N}{\delta }(d(x,{{x}_{j}}))$
(14) 其中
$\delta (z)=\left\{ \begin{array}{*{35}{l}} \begin{align} & 1,\quad z\le \theta \\ & 0,\quad 其他 \\ \end{align} \\ \end{array} \right.$
(15) 数据点x的离散度大小ζ采用文献[24]的相关公式进行衡量.
定义 2 (离散度). 任一点xi的离散度ζ定义为该点到比该点密度更大的其他点的最小距离,即:
${\zeta _i} = \mathop {\min }\limits_{{\rho _{{x_i}}} < {\rho _{{x_j}}}} d({x_i},{x_j}),\forall {x_j} \in X$
(16) 可以看出,两个指标中,密度具有局部性,离散度具有全局性.下面给出利用这两个指标对数据集进行LS-SVM消减的基本思路.
图 1给出了利用密度和离散度进行LS-SVM稀疏化的支持向量集选择示意图. 其中,图 1 (a)为原始LS-SVM的决策超平面f(x)(图中细实线)及两个类中心超平面(f(x)=+1及 f(x)=-1,图中长划线),图 1 (b)为稀疏化后LS-SVM的决策超平面g(x) (图中点划线)及两个类中心超平面(g(x)=+1及g(x)=-1,图中双点划线).由于决策超平面由两个类中心超平面决定,因此,只要找到可以确定两个中心超平面的数据点并将其纳入到S集合中,就可以实现LS-SVM的稀疏化.由于稀疏化后需要的支持向量数量比较少,因此将高密度点作为支持向量可以使得类中心超平面的定位更具有精确性.所以,尽量选取高密度点(如黑色数据点)进入S集合是很合理的思路.但是,若仅考虑密度,则容易造成集中在某个高密度区域的点(如灰色点)大量进入S集合从而使得S集合丧失全局性.与之对应,如果选取密度虽然较小但是在离散度上更大的点(如条纹点)代替灰色点,就能够使得稀疏化后的决策超平面更接近原始超平面.因此,同时考虑密度和离散度是选择S集合元素的关键依据.若将同时具有高密度和离散度的点称为全局代表点,则选择全局代表点作为S集合元素的算法是本文的主要贡献之一.
图 1 稀疏化LS-SVM的支持向量选择示意图Fig. 1 Description of support vector selection of sparse LS-SVM若将ρ和ζ看作两个维度,那么全部数据在该二维空间中主要分布在3块区域. 图 2给出了一个二维数据在ρ-ζ空间中的分布示意图. 其中,图 2 (a)表示的是数据在原始空间中的分布,图 2 (b)表示的是数据在ρ-ζ 空间中的分布.明显地,分布在I区的数据点的特征是密度和离散度都比较大,是具有全局代表性的数据点.分布在II区的数据点的特征是密度很小离散度很高,一般是离群点或者是噪声点.在III区的数据点,其特征是密度比较高,但是离散度较低,一般是在全局代表性点附近的点.因此,合理划分3个区域并且尽量将I区的数据点选择出来作为S集是下面要讨论的问题.
从图 2可以看出,全局代表性点比较稀疏,可以采用离群点发现算法进行获取. 但是,相应算法的时间复杂性较高,很难适应大数据量的要求.为此,我们通过设计全局代表性指标τ来进行全局代表点的选取.
由于ρ和ζ的单位不同,因此首先进行归一化处理,即将ρ和ζ映射到预先给定的区间 $[\eta_{\min},\eta_{\max}] (\eta_{\min},\eta_{\max}>0)$ ,并设映射后的值为 ρ和ζ.则任一点xi 的全局代表性指标τi 可以按照如下两式之一进行计算:
${{\tau }_{i}}=\min ({{{\bar{\rho }}}_{i}},{{{\bar{\zeta }}}_{i}})$
(17) ${{\tau }_{i}}={{{\bar{\rho }}}_{i}}\times {{{\bar{\zeta }}}_{i}}$
(18) 可知,τi越大,对应的xi的全局代表性就越高.在此基础上,我们给出全局代表点选取算法(Global representative point selection,GFPS),具体过程描述如算法1所示.
算法 1. GFPS
输入:数据集X,核函数k,阈值θ,数量L;
输出:选出的代表点集合S;
1) 根据式(13)计算 $d({ x}_i,{ x}_j)$ ;
2) 根据式(14),(16)计算ρ,ζ;
3) 归一化ρ,ζ;
4) 根据式(17)或(18)计算τ;
5) 按照从大到小对τ排序;
6) 取前L个数据形成S;
7) return S.
可以看出,算法GFPS的计算过程是一个非迭代过程,其主要过程包括3个顺序步骤:一是计算特征空间中任意两个点之间的距离,时间复杂度为 ${\rm O}(N^2)$ ;二是计算每个点的ρ和ζ,时间复杂度为 ${\rm O}(N^2)$ ;三是对序列τ进行排序,并一次性地抽取序列中最前面L个数据点形成支持向量集,在使用快速排序等较快的排序算法的情况下,其时间复杂度是 ${\rm O}(N{\rm log}N)$ .因此,算法GFPS的时间复杂度是 ${\rm O}(N^2)$ .
2.3 GRS-LSSVM 算法
在分类问题的LS-SVM稀疏化过程中,由于各类数据的分布差异较大,为了防止出现S集中仅包含某一类数据的情况,我们按照训练集全部数据的类别比例来分配S集合中各类代表点的数量.具体计算公式如下:
$L_i=\max(1,\text{round}(L\times \frac{N_i}{N})) $
(19) 其中,Li表示第i类数据中选择的代表点的数量, $\text{round}(\cdot)$ 表示四舍五入函数,Ni表示第i类数据的数量,N表示全体训练集的数量.
综合上面的讨论,我们给出基于全局代表性点选取的LS-SVM消减算法,具体过程描述如 算法2所示.
算法 2. GRS-LSSVM
输入:训练集X,Y,参数C,核函数k,阈值θ+,θ-,稀疏化后的支持向量集的大小L;
输出:消减后的支持向量集S,对应的系数β,b;
1) 根据式(19)计算两类数据点在S集中的数据量L+,L-;
2) $S_+=\text{GFPS}(X_+,k,L_+,\theta_+)$ ;
3) $S_-=\text{GFPS}(X_-,k,L_-,\theta_-)$ ;
4) $S=S_+\cup S_-$ ;
5) 根据式(12)计算β,b;
6) return S,β,b.}
算法2中,X+,X-分别是训练集中属于正负类的数据集,θ+,θ-是分别用于正负类的距离阈值.明显地,虽然GRS-LSSVM算法没有采用迭代方式来构造S集合,但随着L的增加,S集合包含的重要数据点的数量将逐步增加最终包含全部数据点从而收敛于LS-SVM.
从计算复杂度来看,该算法的主体是2次GFPS算法的调用和1次求解支持向量系数.由上述分析知,GFPS算法的时间复杂度为 ${\rm O}(N^2)$ .求解支持向量系数主要是进行1次矩阵逆计算,时间复杂度是 ${\rm O}(L^3)$ . 由于L<<N,这部分的计算对总体时间复杂度的影响很小,可以忽略不计.因此,GRS-LSSVM算法的总体时间复杂度为 ${\rm O}(N^2)$ .
3. 实验结果及分析
为了测试本文提出的算法性能,我们利用UCI中的真实数据集对各种算法进行测试并对结果进行分析.
3.1 数据集的选取
我们使用表 1中来自UCI (University of California Irvine machine learning repository)的4个数据集作为实验分析的数据集.这4个数据集的数据都来自真实数据,具有实际应用背景.其中,由于LR数据集包含多类数据,因此在本文中,采用一对多的分类方式,取字母B作为一类,其他数据作为另一类进行测试.
表 1 数据集描述表Table 1 Description of datasets数据集名称 数据量 数据维度 两类比例 Breast cancer wisconsin (BCW) 684 9 445 : 239 Banknote authentication (BA) 1 372 4 610 : 762 Musk (MK) 7 074 166 1 224 : 5 850 Letter recognition (LR) 20 000 16 789 : 19 211 3.2 评价指标
在分析对照的指标上,我们选择运行时间(Time)和错误率(Error ratio)作为算法性能的衡量指标.其中,运行时间是指全部计算数据加载入内 存到算法给出稀疏化后的支持向量集S及对应的系数β和b的时间跨度,单位为秒(s).错误率是指分类错误的数据 数量占全部数据量的百分比,在本文中采用10- 折交叉确认误差来进行衡量.稀疏度也是衡量一个算法的重要指标,其定义为稀疏化后的支持向量的个数与训练集大小的比值.当训练集大小固定时,稀疏度和文中使用的稀疏化后保留的支持向量的个数L具有等价性.因此,为了方便比较不同算法在各种稀疏度要求下的性能,将L作为算法的控制参数对各个算法进行试验测试.
3.3 对照算法
在本文的实验中,我们使用SLS-SVM (Sparse LS-SVM) [6]和RR-LSSVR (Recursive reduced least squares support vector regression) [12]以及ISLS-SVM (Iterative sparse LS-SVM) [14]作为对照算法. 同时,为了进一步分析算法的特点,我们使用SVM及LS-SVM作为稀疏支持向量机及非稀疏支持向量机的基准算法,进行对照分析. 其中,SLS-SVM算法中每一步消减的支持向量的数量设为1 %,RR-LSSVR中ε=0.00001.
3.4 实验设计
为了正确衡量各个算法的性能,对所有数据集都采用了10- 折交叉验证方法进行测试. 核函数采用RBF kernel.各个参数针对不同的算法进行了优化调整,以便比较不同算法在最优情况下的性能特点.由于每个数据集包含的数据量相差很大,同时考虑到计算机的内存容量限制及对照方便,在将数据集划分为训练集和测试集后,从训练集中按照等概率原则抽取预定数量的数据形成计算时的训练集.其中,BCW的预定数量为500,BA为1 000,MK为2 000,LR为4 000.针对每一个数据集都进行10次10- 折交叉验证并使用各个指标的平均值作为结果进行对比.
全部算法在Matlab 2010a环境中编程实现,并运行在一台内存为4 GB,CPU为i5 3270的机器上.
3.5 实验结果分析
图 3给出了不同算法在不同数据集上的错误率,图 4给出了错误率的标准差,图 5是各个算法的运行时间结果,由于各个算法的时间差异比较大,为了能够显示在一张图中,我们使用了对数坐标,图 6是每个算法运行时间的标准差.在各图中,(a) ~ (d)分别对应数据集BCW、BA、MK和LR.
SVM和LS-SVM在各个数据集上的实验结果如表 2所示,其中NS是指算法获得的决策超平面包含的支持向量的个数.从表 2可知,SVM和LS-SVM的泛化能力基本相同,对于同一数据集的错误率基本保持一致.在运行时间上虽然LS-SVM比SVM略长,但是基本还保持在同一数量级.但是,支持向量个数差别很大,LS-SVM包含了训练集的全部向量,SVM包含的支持向量的个数相对比较稀疏.虽然SVM具有稀疏性,但是稀疏度也基本维持在20 %至40 %左右.
表 2 SVM和LS-SVM结果Table 2 Results of SVM and LS-SVM数据集 SVM LS-SVM Error ratio (%) Time (s) NS Error ratio (%) Time (s) NS BCW 3.0 (±0.01) 0.02 (±0.005) 93.2 (±0.85) 3.0 (±0.010) 0.020 (±0.001) 500 (±0) BA 2.4 (±0.01) 0.09 (±0.005) 418.8 (±1.96) 1.0 (±0.010) 0.072 (±0.007) 1 000 (±0) MK 5.7 (±0.04) 0.30 (±0.010) 642.2 (±6.40) 5.1 (±0.100) 0.380 (±0.020) 2 000 (±0) LR 1.0 (±0.04) 1.32 (±0.050) 1706.0 (±79.0) 1.0 (±0.035) 1.780 (±0.050) 4 000 (±0) 首先,从稀疏度来看各个算法的特征. SLS-SVM,RR-LSSVR以及GRS-LSSVM都可以根据给定的L进行稀疏化,使得稀疏化后的支持向量的个数达到任意指定的值. 但是ISLS-SVM不具有这种能力,当给定的L小于某一阈值时,该算法不能给出结果.换句话说,ISLS-SVM具有最大稀疏度限制,该限制使得该算法在稀疏度要求比较高的情况下不能使用.观察算法到达稳定错误率时所需要的稀疏度大小,一般来讲,其需要的稀疏度大小为GRS-LSSVM < ISLS-SVM < SLS-SVM < RR-LSSVR.这说明GRS-LSSVM在一个非常小的稀疏度要求时就可以达到其稳定状态,即该算法稳定时的稀疏度阈值要小于其他算法.在实际应用中给定的稀疏度要求非常高的情况下,该算法能最先达到其稳定值.虽然该算法在稳定时的错误率并不是最小,但是其错误率的大小也已经在一个可以接受的范围内.这表明,GRS-LSSVM算法的稀疏化能力比较出色.在很多的实际应用中,对于错误率的要求不是那么强烈,但是对于稀疏化后的支持向量集的大小要求比较高,这种情况下,尤其是要求稀疏度特别大的情况下,其他算法往往不能胜任,而GRS-LSSVM还可以满足要求.出现这种情况的原因在于,该算法选取的是最具有全局代表性的数据点作为支持向量,即便稀疏度要求比较高,由于选择的点具有全局代表性,因此依然能够达到较好的效果.
其次,从错误率方面来看各个算法的特征.全部算法首先表现出几个共同的特征.首先,当给定的支持向量的个数达到某个阈值时,全部算法都能下降到一个非常低的接近LS-SVM的错误率水平.其次,在达到该阈值后,即便支持向量的个数增加,每个算法在错误率上也没有很大的提高,并保持在一个非常稳定的错误率上.最后,错误率标准差的变化和错误率的变化相类似,在达到并超过阈值后,将维持在一个非常小的范围内并保持稳定. 在未达到稳定值之前,SLS-SVM的错误率最高,RR-LSSVR次之,GRS-LSSVM最小,且比较接近稳定值.这表明即便要求的稀疏度高于算法的稀疏度阈值,GRS-LSSVM也可以提供具有相对较好错误率的决策函数. ISLS-SVM由于在高稀疏度下不能计算,所以不参与比较.当达到稳定值后,4个算法的错误率的排序一般保持SLS-SVM < ISLS-SVM < GRS-LSSVM < RR-LSSVR.虽然GRS-LSSVM的错误率不是最低,但是其错误率也已经接近LS-SVM的错误率,并且和其他算法的错误率相差不大.总体来讲,当稀疏度要求比较低的时候,该算法在错误率的表现上并不突出,但是当稀疏度要求比较高时,尤其是稀疏度要求的值不能满足其他算法达到稳定性值的情况下,该算法达到的错误率要比其他方法要好.原因在于GRS-LSSVM用最具有全局代表性的数据点构成支持向量集,在稀疏度高的情况下,可以通过较少的数据点来达到相对较好的分类效果,但是在达到稳定后,新增的节点对其决策超平面的改变贡献会很小,所以相比较其他算法,效果相对稍弱.
最后,从计算复杂性上来进行分析.明显的,4个算法的表现完全不同. SLS-SVM总体上呈现出随稀疏度下降,计算时间缓慢降低的趋势.原因是SLS-SVM采用的是向量消去方法,稀疏度下降,说明最终的支持向量集包含的向量数量比较多,被消减的向量比较少.因此,所需要的计算时间也会减少. RR-LSSVR的计算时间随着稀疏度的下降,时间呈爆炸式增长.原因在于RR-LSSVR采用的是增量式稀疏化模式,由于每次只能向支持向量集添加一个向量,导致其计算复杂度随着训练集的增长而增长,同时,稀疏度的下降,也导致其计算复杂度的增长. 对于ISLS-SVM,其计算时间会随着稀疏度的下降而降低,其主要原因是该算法本质上是一种删除式稀疏化方法,在稀疏度要求比较高的时候,需要删除的向量数量比较大,这样迭代的次数会比较多,同时,在迭代中矩阵运算出现奇异矩阵的可能性也比较大,这些都会让运算时间比较长. 对于GRS-LSSVM,其运算时间表现出3个特征: 1)在训练集固定的情况下,其运算时间并没有随稀疏度的变化而发生变化; 2)不同数据集的数据量虽然差别很大,但是,该算法的运算时间并没有巨大的变化; 3)该算法的时间稳定性比较好,计算时间的标准差比较小.具有这3个特征的原因在于该 算法没有采用迭代方式进行支持向量的选择,而是在计算出全部数据点的全局代表性值后,一 次性地根据代表性的大小选择支持向量集,因此其计算时间会比较短.
4. 总结
在本文中,我们针对LS-SVM稀疏化问题,提出了一种基于全局代表点提取的稀疏化算法. 该算法的思想是通过数据点的局部密度和全局分布性来确定数据的代表性,然后按照代表性的大小直接选择稀疏化后的支持向量,并在这些支持向量的基础上计算稀 疏化后的决策超平面.由于不需要迭代选择支持向量,因此,该方法具有计算复杂性低、 性能稳定、稀疏度高等特点.对LS-SVM稀疏化研究提供了新的思路.实验研究也证明了该算法的特点.
-
图 4 维诺图顶点与相邻传感器节点的几何关系
Fig. 4 Geometric relationship between Voronoi vertexes and adjacent sensor nodes
图 7 实验1中本文方法规划出的最优路径
Fig. 7 Optimal path planned by the method in this paper in Experiment 1
图 8 实验2中本文方法规划出的最优路径
Fig. 8 Optimal path planned by the method in this paper in Experiment 2
图 9 实验3中本文方法规划出的最优路径
Fig. 9 Optimal path planned by the method in this paper in Experiment 3
图 10 实验1中三种方法所规划路径的长度比较
Fig. 10 Comparison of path length by three methods in Experiment 1
图 11 实验2中三种方法所规划路径的长度比较
Fig. 11 Comparison of path length by three methods in Experiment 2
图 12 实验3中三种方法所规划路径的长度比较
Fig. 12 Comparison of path length by three methods in Experiment 3
图 15 以Delaunay三角形重心作为数据收集点的能耗分布
Fig. 15 Energy consumption distribution at Delaunay triangle´s center
图 16 以Delaunay三角形内随机点作为数据\\收集点的能耗分布
Fig. 16 Energy consumption distribution at Delaunay triangle´s random points
表 1 传感器节点与维诺图顶点间的支配关系
Table 1 Dominating relationship between sensor nodes and Voronoi vertexes
节点 顶点 节点 顶点 s1 v7 ,v10 s2 v6 ,v7 ,v8 s3 v1 ,v10 ,v11 s4 v7 ,v8 ,v9 ,v10 ,v11 s5 v1 ,v2 s6 v3 ,v6 s7 v3 ,v4 ,v5 s8 v1 ,v2 ,v4 ,v5 ,v9 ,v11 s9 v3 ,v5 ,v6 ,v8 ,v9 s10 v2 ,v4 
下载: 导出CSV
表 2 通信模型参数值
Table 2 Parameter value of communication model
参数 值 节点发射或接收电路能耗系数es (nJ/bit) 50 节点功率放大能耗系数εs (pJ/bit m2) 100 移动基站广播数据量k1 (bit) 100 传感器节点发送数据量k2 (bit) 10000 基站航行速v (m/s) 5
下载: 导出CSV
表 3 分组实验所得结果
Table 3 Grouping experiment results
实验分组 路径长度(m) 网络总能耗(10-3J) 能量效率(J-1) (a) 16.559 5.076 7.181 实验1 (b) 23.507 10.124 0.897 (c) 29.993 15.174 0.164 (a) 51.492 12.751 2.642 × 10-3 实验2 (b) 69.923 20.302 4.159 × 10-5 (c) 75.293 25.348 1.138 × 10-5 (a) 409.118 27.05 1.077 × 10-34 实验3 (b) 456.700 39.75 5.398 × 10-39 (c) 532.231 52.525 1.124 × 10-45
下载: 导出CSV
表 6 三种方法所规划路径的能量效率比较
Table 6 Comparison of total energy efficiency by three methods
实验分组 能量效率(J-1) 本文方法 文献[12]方法 文献[16]方法 (a) 7.181 2.127 × 10-3 0.288 实验1 (b) 0.897 4.821 × 10-4 5.634 × 10-3 (c) 0.164 6.789 × 10-5 1.556 × 10-3 (a) 2.642 × 10-3 1.441 × 10-15 6.675 × 10-7 实验2 (b) 4.159 × 10-5 4.117 × 10-18 7.247 × 10-9 (c) 1.138 × 10-5 1.966 × 10-19 1.218 × 10-9 (a) 1.077 × 10-34 0 2.206 × 10-53 实验3 (b) 5.398 × 10-39 0 3.009 × 10-63 (c) 1.124 × 10-45 0 5.642 × 10-77
下载: 导出CSV
表 7 实验1(a)中,传感器节点的能耗及方差值
Table 7 Energy consumption and variance of sensor nodes in Experiment 1(a)
实验1(a) 能耗(10-3J) 方差(10-12J2) s1 s2 s3 s4 s5 s6 s7 s8 s9 s10 ∑ 本文方法的维诺图顶点 0.5087 0.5070 0.5087 0.5087 0.5076 0.5070 0.5070 0.5070 0.5070 0.5076 5.076 0.543 Delaunay三角形重心 0.5081 0.5062 0.5093 0.5083 0.5079 0.5073 0.5060 0.5079 0.5072 0.5071 5.075 0.879 Delaunay三角形内随机点 0.5098 0.5097 0.5079 0.5058 0.5083 0.5051 0.5062 0.5089 0.5094 0.5071 5.078 2.198
下载: 导出CSV
-
[1] Gkikopouli A, Nikolakopoulos G, Manesis S. A survey on underwater wireless sensor networks and applications. In:Proceedings of the 20th Mediterranean Conference on Control and Automation. Barcelona, Spain:IEEE, 2012.1147-1154 https://www.researchgate.net/publication/281716899_Multihops_Fitting_Approach_for_Node_Localization_in_Underwater_Wireless_Sensor_Networks [2] Davis A, Chang H. Underwater wireless sensor networks. In:Proceedings of the 2012 Oceans Conference. Virginia, USA:IEEE, 2012.1-5 http://eprints.qut.edu.au/view/types/conference=5Fpaper/2012.default.html [3] Tunca C, Isik S, Donmez M Y, Ersoy C. Distributed mobile sink routing for wireless sensor networks:a survey. IEEE Communications Surveys and Tutorials, 2014, 16(2):877-897 doi: 10.1109/SURV.2013.100113.00293 [4] 罗旭, 柴利, 杨君. 无线传感器网络下静态水体中的近岸污染源定位. 自动化学报, 2014, 40(5):849-861 http://www.aas.net.cn/CN/abstract/abstract18353.shtmlLuo Xu, Chai Li, Yang Jun. Offshore pollution source localization in static water using wireless sensor networks. Acta Automatica Sinica, 2014, 40(5):849-861 http://www.aas.net.cn/CN/abstract/abstract18353.shtml [5] Wang J, Yang X Q, Li B, Lee S Y, Jeon S K. A mobile sink based uneven clustering algorithm for wireless sensor networks. Journal of Internet Technology, 2013, 14(6):895-902 http://cn.bing.com/academic/profile?id=2261891850&encoded=0&v=paper_preview&mkt=zh-cn [6] Nizhamudong Y, Nakaya N, Hagihara Y, Koui Y. Performance evaluation of route cost for wireless sensor networks with a mobile sink. In:Proceedings of the 2011 SICE Annual Conference. Tokyo, Japan:IEEE, 2011.2029-2031 [7] Liang W F, Schweitzer P, Xu Z C. Approximation algorithms for capacitated minimum forest problems in wireless sensor networks with a mobile sink. IEEE Transactions on Computers, 2013, 62(10):1932-1944 doi: 10.1109/TC.2012.124 [8] Saad E M, Awadalla M H, Darwish R R. A data gathering algorithm for a mobile sink in large-scale sensor networks. In:Proceedings of the 4th International Conference on Wireless and Mobile Communications. Athens, Greece:IEEE, 2008.207-213 [9] Liang W F, Luo J. Network lifetime maximization in sensor networks with multiple mobile sinks. In:Proceedings of the 36th Conference on Local Computer Networks. Bonn, Germany:IEEE, 2011.350-357 http://dl.acm.org/citation.cfm?id=2195216.2195437 [10] Nagamalar T, Rangaswamy T R. Energy efficient cluster based approach for data collection in wireless sensor networks with multiple mobile sink. In:Proceedings of the 2015 International Conference on Industrial Instrumentation and Control. Pune, India:IEEE, 2015.348-353 [11] Shah R C, Roy S, Jain S, Brunette W. Data MULEs:modeling and analysis of a three-tier architecture for sparse sensor networks. Ad Hoc Networks, 2003, 1(2-3):215-233 doi: 10.1016/S1570-8705(03)00003-9 [12] Chatzigiannakis I, Kinalis A, Nikoletseas S. Efficient data propagation strategies in wireless sensor networks using a single mobile sink. Computer Communications, 2008, 31(5):896-914 doi: 10.1016/j.comcom.2007.12.011 [13] Ma M, Yang Y Y. Data gathering in wireless sensor networks with mobile collectors. In:Proceedings of the 2008 IEEE International Symposium on Parallel and Distributed Processing. Miami, USA:IEEE, 2008.1-9 http://dsn.sagepub.com/content/10/9/698452.full [14] Luo J, Hubaux J P. Joint mobility and routing for lifetime elongation in wireless sensor networks. In:Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Societies. Miami, USA:IEEE, 2005.1735-1746 [15] 石高涛, 廖明宏. 传感器网络中具有负载平衡的移动协助数据收集模式. 软件学报, 2007, 18(9):2235-2244 doi: 10.1360/jos182235Shi Gao-Tao, Liao Ming-Hong. Movement-assisted data gathering scheme with load-balancing for sensor networks. Journal of Software, 2007, 18(9):2235-2244 doi: 10.1360/jos182235 [16] Zhu R B, Qin Y Y, Wang J Q. Energy-aware distributed intelligent data gathering algorithm in wireless sensor networks. International Journal of Distributed Sensor Networks, 2011, 2011:Article ID 235724 http://cn.bing.com/academic/profile?id=1998032303&encoded=0&v=paper_preview&mkt=zh-cn [17] Salarian H, Chin K W, Naghdy F. An energy-efficient mobile-sink path selection strategy for wireless sensor networks. IEEE Transactions on Vehicular Technology, 2014, 63(5):2407-2419 doi: 10.1109/TVT.2013.2291811 [18] Heinzelman W R, Chandrakasan A, Balakrishnan H. Energy-efficient communication protocol for wireless microsensor networks. In:Proceedings of the 33rd Annual Hawaii International Conference on System Sciences. Hawaii, USA:IEEE, 2000. http://cn.bing.com/academic/profile?id=1966877298&encoded=0&v=paper_preview&mkt=zh-cn [19] Voronoi G M. Nouvelles applications des paramétres continus á la théorie des formes quadratiques deuxiéme memoire:recherches sur les parallélloédres primitifs. Journal Für Die Reine und Angewandte Mathematik, 1908, 1908(134):198-287 http://cn.bing.com/academic/profile?id=1520127302&encoded=0&v=paper_preview&mkt=zh-cn [20] Mirzargar M, Entezari A. Voronoi splines. IEEE Transactions on Signal Processing, 2010, 58(9):4572-4582 doi: 10.1109/TSP.2010.2051808 [21] Garrido S, Moreno L, Blanco D, Jurewicz P P. Path planning for mobile robot navigation using Voronoi diagram and fast marching. International Journal of Robotics and Automation, 2011, 2(1):42-64 http://yadda.icm.edu.pl/yadda/element/bwmeta1.element.ieee-000004058742 [22] Ok K, Ansari S, Gallagher B, Sica W, Dellaert F, Stilman M. Path planning with uncertainty:Voronoi uncertainty fields. In:Proceedings of the 2013 IEEE International Conference on Robotics and Automation. Karlsruhe:IEEE, 2013.4596-4601 http://cn.bing.com/academic/profile?id=2368403481&encoded=0&v=paper_preview&mkt=zh-cn [23] 夏娜, 倪成春, 徐朝农, 丁胜, 郑榕. 逆向捕获时间差的Voronoi声源定位机制. 通信学报, 2013, 34(11):140-152 http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB201311016.htmXia Na, Ni Cheng-Chun, Xu Chao-Nong, Ding Sheng, Zheng Rong. Voronoi acoustic source localization mechanism based on counter captured time difference. Journal on Communications, 2013, 34(11):140-152 http://www.cnki.com.cn/Article/CJFDTOTAL-TXXB201311016.htm [24] 郭帅, 马书根, 李斌, 王明辉, 王越超. 基于Voronoi地图表示方法的同步定位与地图创建. 自动化学报, 2011, 37(9):1095-1104 http://www.aas.net.cn/CN/abstract/abstract17532.shtmlGuo Shuai, Ma Shu-Gen, Li Bin, Wang Ming-Hui, Wang Yue-Chao. Simultaneous localization and mapping through a Voronoi-diagram-based map representation. Acta Automatica Sinica, 2011, 37(9):1095-1104 http://www.aas.net.cn/CN/abstract/abstract17532.shtml [25] Bourgeois N, Croce F D, Escoffier B, Paschos V T. Fast algorithms for min independent dominating set. Discrete Applied Mathematics, 2013, 161(4-5):558-572 doi: 10.1016/j.dam.2012.01.003 [26] 路纲, 周明天, 唐勇, 吴振强, 裘国永, 袁柳. 任意图支配集精确算法回顾. 计算机学报, 2010, 33(6):1073-1087 doi: 10.3724/SP.J.1016.2010.01073Lu Gang, Zhou Ming-Tian, Tang Yong, Wu Zhen-Qiang, Qiu Guo-Yong, Yuan Liu. A survey on exact algorithms for dominating set related problems in arbitrary graphs. Chinese Journal of Computers, 2010, 33(6):1073-1087 doi: 10.3724/SP.J.1016.2010.01073 [27] Chen S M, Chien C Y. Solving the traveling salesman problem based on the genetic simulated annealing ant colony system with particle swarm optimization techniques. Expert Systems with Applications, 2011, 38(12):14439-14450 doi: 10.1016/j.eswa.2011.04.163 [28] 饶卫振, 金淳. 基于求解TSP问题的改进贪婪算法. 运筹与管理, 2012, 21(6):1-9 http://www.cnki.com.cn/Article/CJFDTOTAL-YCGL201206003.htmRao Wei-Zhen, Jin Chun. An improved greedy heuristic based on solving traveling salesman problem. Operations Research and Management Science, 2012, 21(6):1-9 http://www.cnki.com.cn/Article/CJFDTOTAL-YCGL201206003.htm [29] Hassin R, Keinan A. Greedy heuristics with regret, with application to the cheapest insertion algorithm for the TSP. Operations Research Letters, 2008, 36(2):243-246 doi: 10.1016/j.orl.2007.05.001 [30] Qin H S, Zhou S L, Huo L, Luo J. A new ant colony algorithm based on dynamic local search for TSP. In:Proceedings of the 5th International Conference on Communication Systems and Network Technologies. Gwalior, India:IEEE, 2015.913-917 [31] Wang P D, Tang Y L, Li Y, Yang X X. Improved ant colony algorithm for traveling salesman problems. In:Proceedings of the 24th Chinese Control and Decision Conference. Taiyuan, China:IEEE, 2012.660-664 期刊类型引用(9)
1. 熊光明，于全富，胡秀中，周子杰，许佳慧. 考虑平台特性的多层建筑物内履带式无人平台运动规划. 兵工学报. 2023(03): 841-850 . 
百度学术2. 闫敬，张志成，杨晛，商志刚，关新平. 水下网络系统定位与控制联合设计：研究现状与发展趋势. 哈尔滨工程大学学报. 2023(11): 1950-1962 . 百度学术3. 王宁，韩雨晓，王雅萱，王天海，张漫，李寒. 农业机器人全覆盖作业规划研究进展. 农业机械学报. 2022(S1): 1-19 . 百度学术4. 闫敬，关新平，罗小元，杨晛. 水下信息物理系统探测–通信–控制一体化:挑战与进展. 控制理论与应用. 2022(11): 1996-2008 . 百度学术5. 徐姗姗. 图匹配算法激光扫描点云树干分割. 中国图象图形学报. 2021(05): 1095-1104 . 百度学术6. 郭银景，侯佳辰，吴琪，苑娇娇，吕文红. AUV全局路径规划环境建模算法研究进展. 舰船科学技术. 2021(17): 12-18 . 百度学术7. 涂文章，蒋立宇，何力. 基于维诺图的路径规划方法. 广东化工. 2019(14): 70+58 . 百度学术8. 陈孝如. 无线传感器网络移动节点路径规划方法仿真. 计算机仿真. 2019(08): 262-265 . 百度学术9. 万方，周风余，尹磊，王玉刚，陈科，沈冬冬. 基于电势场法的移动机器人全局路径规划算法. 机器人. 2019(06): 742-750 . 百度学术其他类型引用(14)
-
下载:
计量
- 文章访问数: 2254
- HTML全文浏览量: 276
- PDF下载量: 1292
- 被引次数: 23
