基于支持向量机的WSN能量感知路由算法

王杰 张伟 马玉洁

摘要：机器学习（ML）技术在无线传感器网络（WSNs）的路由协议中应用极大地帮助传感器节点解决了其能量消耗问题。 众多专家学者已经提出许多相关的解决方案，该类算法有效的优化了资源利用率，达到了延长网络寿命的效果。该文提出了一种基于支持向量的高效分簇协议，该算法能够有效地将传感器节点分配到最近的Sink节点，同时平衡簇头之间的能量消耗。 该协议与低功耗自适应集簇分层型协议（LEACH）在NS-2仿真软件上进行仿真和测试。实验对比发现，在无线传感器网络中表现出更好的资源利用率。

关键词：WSN；路由协议；分簇；LEACH

中图分类号：TP393 文献标识码：A 文章编号：1009-3044（2018）09-0046-03

无线传感器网络通常部署在复杂环境中，用于监测关键信息；如地震，温度和洪水情况。因此在传感器工作的条件下为其补充能量实现难度较大；意味着优秀的路由协议能够有效地利用电池资源，有助于延长WSN的使用寿命。机器学习（ML）算法能够融合WSN的资源管理，比传统的路由算法更为有效。先前众多专家学者在WSN的路由协议中引入了几种ML算法来在无线传感器网络中规划路由； 该方法能够尽量降低不规则路线造成的节点能量消耗。

为了延长网络生存时间，WSN被划分成具有一个簇头和多个传感器节点的簇域。每个簇域都会通过某种算法产生一个簇头（Sink节点），负责收集和处理簇内传感器节点的原始数据，并将处理后的数据发送给基站（BS）。该路由方式能够降低各个传感器節点的能耗。该类型的聚类算法被称为分层路由协议（Hierarchical Routing Protocols）。 本文引入了一个使用支持向量机（SVM）的分层路由协议。并通过实验仿真与低功耗自适应集簇分层型协议（LEACH）相比较。

1 相关工作

Asa Ben-Hur等人提出一种基于支持向量的向量聚类算法[1]Support Vector Clustering，SVC），该算法能够有效保证网络中的每个簇域都拥有平滑的簇边界。创新性在于：该算法所产生的簇域不同于其他聚类算法所生成几何形状的簇域。并且支持优化聚类方案。文献[2]中，作者提出了使用支持向量机的聚类算法； 并通过执行名词短语和新闻文章聚类对算法进行测试，并证明该聚类是NP-hard问题，并评估了学习时使用的近似方法。实验证明SVM聚类可以提供最优的聚类解决方案。

支持向量基于学习算法，一般用于求解分类和回归问题。该技术由科特斯和瓦普尼克[3]于1995年首先提出。自提出之日起，它一直是解决许多问题的学习技术之一。虽然支持向量机被广泛用于分类和回归，但是众多文献表明它有助于解决聚类问题。

支持向量机通过在平面上绘制一条直线来分离两组或多组数据点，从而可以求得最佳的分离线（分离线与任何一组的数据点都不会太接近，为了避免造成噪声，影响泛化；最佳线要尽可能远离数据点）。通过以下示例可以更好地理解SVM；假设我们在超平面上有两组数据，如图1所示。

从上图可以看出，平面内可以画出多条线将两组数据点分开。支持向量机的主要目标就是绘制一条线，进而可以最优地分离两个组。由此我们可以得出结论：SVM训练系统对数据集进行分类，使得所有组或类之间的最小距离更大。该算法通过迭代直到达到期望的最优线[3]；图2则描绘了最佳线的选取。

1.1 SVM的优缺点

优点：①与K-Means算法不同，SVM更利于处理高维度的平面；②在提供的数据样本数量少于维度数量的情况下，这是相当不错的；③支持向量机被证明是有效的。

缺点：在为分类提供的特征数量超过提供的数据样本数量的情况下，SVM的性能下降。

2 无线传感器网络路由协议

无线传感器网络的主要工作是信息监测和评估。并将有效信息传输至基站。如果网络内的每个传感器节点都将感知到的信息直接发送至基站（BS），则网络生存时间较短。因此，多跳传输的思想被认为是能够最大限度地提高远离BS传感器节点的寿命[4]。 关于解决WSN能耗问题的各类算法中，路由算法设计是其重要组成部分；该算法负责构建和维护节点之间的路由路径，优良的路由协议设计能够使 WSN最大限度地减少资源利用率。

2.1 分簇协议

因为它具有良好的节能行为。无线传感器网络的分簇类路由协议在过去数十年的研究中取得了较大进展，在分层协议中，传感器节点被分成许多簇，每个簇选举一个簇首。传感器节点负责检测数据并将其发送到各自的簇头。簇首接收数据，汇总并发送给基站。 一般来说，簇头比网络中的普通传感器节点具有更大的权限。因此，网络的总体能量可以保持较高水平。下面列出了一些著名的分层路由协议：

①低功耗自适应集簇分层型协议（LEACH）

②传感器信息系统中的低效收（PEGASIS）

③固定簇半径的分簇协议（HEED）

④阈值敏感节能传感器网络协议（TEEN）

⑤自适应周期性阈值敏感节能传感器网络协议（APTEEN）

2.2 本文所提算法

本文所提基于支持向量的路由算法步骤说明如下：

Step1：Begin

Step2：将每个传感器节点分配到最近的簇头；

Step3：Set i = 0；

Step4：计算传感器节点到其各自簇头的平均距离；

Step5：如果（实际距离）/（最小距离）<1（阀值），则转到Step8，否则继续Step6；

Step6：将簇头移动至平均距离坐标位置；

Step7：Set i = i + 1；

Step8：如果i ≠ 5，跳转至Step4；

Step9：End

3 实验仿真

为了测试性能指标，本文所提议协议在网络模拟器2（NS-2）中执行。我们将算法放在三种不同场景中进行模拟仿真，分别是小型，中型和大型无线传感器网络， 小规模网络包含5个簇域，每个簇域内含5个传感器节点，中等规模网络包含7个簇域，每个簇域包含7个传感器节点，大规模网络包含10个簇域，每个簇域包含10个传感器节点。 图3，图4和图5分别描述了所有三种情景下NS-2仿真的节点布局。表1示出了分别用于监督和无监督学习算法的模拟参数。

4 结论

通过分析能量消耗（图6）和分组延迟比PDR（图7）来比较分析两种算法，仿真结果表明，在所有的部署场景中SVM的网络生存时间都优于LEACH算法，并且，数据包延时时间更低。

从上面的分析可以得出结论：基于SVM的路由协议能够有效的延长无线传感器网络的生存时间。并且数据报的通信延时相较其他同类协议更低，该算法是一种有监督的聚类算法，与LEACH相比，它提供了一种有效的聚类技术，可以帮助提高无线传感器网络的资源利用率。

参考文献：

[1] Ben-Hur A， Horn D， Siegelmann H T， et al. Support vector clustering[J]. Journal of Machine Learning Research， 2002， 2（2）：125-137.

[2] Finley T， Joachims T. Supervised clustering with support

vector machines[C]// ICML. 2005：217-224.

[3] N Cristianini， Shawe-taylor. J An. Introduction to Support Vector Machines[J]. 2000， 32（8）：1-28.

[4] Villalba L J， Orozco A L， Cabrera A T， et al. Routing protocols in wireless sensor networks[J]. Sensors， 2009， 9（11）：8399-421.

[5] Pantazis N A， Nikolidakis S A， Vergados D D. Energy-Efficient Routing Protocols in Wireless Sensor Networks： A Survey[J]. IEEE Communications Surveys & Tutorials， 2013， 15（2）：551-591.

[6] 杜海韜， 李强， 丁广太，等. WSN中基于链路质量和节点能量的AODV路由算法研究[J]. 传感技术学报， 2016， 29（7）：1042-1048.

[7] 孙彦清， 彭舰， 刘唐，等. 基于动态分区的无线传感器网络非均匀成簇路由协议[J]. 通信学报， 2014（1）：198-206.

[8] Jiang Y， Shi W， Wang X， et al. A distributed routing for wireless sensor networks with mobile sink based on the greedy embedding[J]. Ad Hoc Networks， 2014， 20（2）：150-162.