基于K中心的无线传感器网络路由协议

A Routing Protocol of Wireless Sensor Networks Based on K-Center

摘要: WSN分簇路由协议具有可扩展的特点，适合于大规模的WSN应用。由于簇首负担较重，簇首分布是影响无线传感器网络性能的关键因素。在随机型的簇首选择算法中，簇首的分布和簇内节点到簇首的距离难以有效控制，不平衡的能耗导致节点过早退出，缩短网络的生命周期。针对簇首的优化选择问题，本文通过K中心的近似算法来挑选簇头，使簇内节点到簇首的距离接近最优。K中心的算法运行时需要一个K值，本文借鉴LEACH协议动态轮转簇头的思路，实现了K中心数量自适应的动态生成。仿真结果表明提出的基于K中心的传感器网络路由协议能有效地延长网络的生命周期。

Abstract: WSN clustering routing protocol has the advantage of good scalability, and is suitable for large-scale applications. As cluster heads are heavy-loaded, their distribution has a great impact on network performance. For randomized clustering algorithm, it is difficult to control cluster heads’ distribution and distance between nodes and cluster heads. Unbalanced energy consumption leads to unavailable nodes and shortens network life cycle. In view of cluster heads selection problem, this pa-per presents a cluster head selection scheme based on the K-center, which controls distance be-tween nodes and cluster heads approximate optimally. K-center algorithm takes as input a parameter K. We use the cluster head rotation mechanism to generate a K value. The final simulation result shows that the proposed WSN routing protocol based on K-center can effectively extend net-work life cycle.

1. 概述

无线传感器网络是由大量传感器节点组成的一种分布式无线自组织网络。为了完成指定的任务，传感器节点需要将监测的数据传送给汇聚节点。由于传感器节点通信能力有限，无线传感器网络中的大多数传感器节点需要通过中间节点采用多跳的方式向汇聚节点进行转发。因此路由成为无线传感器网络中一个关键因素，能否在传感器节点和汇聚节点之间建立高效的传输路径，对无线传感器网络的性能将产生很大的影响 [1] [2] [3] [4] 。

LEACH (Low-Energy Adaptive Clustering Hierarchy)协议 [5] 是一种低功耗自适应分层路由协议。该协议的基本思想是将网络划分成多个簇，簇内的成员节点将所采集的数据发送给簇头，簇头对接收到的数据进行融合处理后，再将数据直接发送给汇聚节点。

尽管LEACH可以改善节点的能耗，但仍存在一些问题。例如：1) 由于每个节点按一定概率成为簇头，LEACH不能保证簇头的数量以及簇头的分布均衡；2) 普通节点和簇头之间，簇头与基站之间的通信距离有时仍然过长，导致节点能耗较大。三层LEACH路由协议 [6] 是在LEACH协议的基础上发展而来的。该方案利用多级传输来控制节点之间的通信距离，通过减少节点间的通信距离节省功耗，延长网络的寿命。基于非均匀分簇的节点能量优化方面的工作还有文献 [7] [8] [9] 。

不同于LEACH协议的分簇模式，PAGASIS协议 [10] 将网络中的所有节点组成一个“链”。该协议要求每个节点都可以获取其他节点的位置信息，并且每个节点仅与距离自己最近的节点通信，采取点到点的方式进行数据传输，使得数据从链头传到链尾(即基站)。

尽管和LEACH协议相比，使用PEGASIS的WSN网络的生命周期更长，但PEGASIS协议也有一些缺点。例如：1) 网络拓扑变化时，必须重建一个新链，这将导致大量的能量消耗；2) 远离链头的那些节点的数据将通过链多次转发到达链头，这将导致高时间延迟。

如上所述：簇头的优化选择和减少节点间的通信距离是WSN路由设计中需要解决的关键问题。本文基于K中心算法 [11] 设计了簇头选取的算法，使簇内节点到簇首的距离接近最优。然而已有的K中心算法运行时需要固定的K值作为运行参数，本文借鉴LEACH协议动态轮转簇头的思路，自适应地生成每轮的K值，控制每轮的K中心数量。仿真结果表明，和LEACH协议、PAGASIS协议相比，提出的基于K中心的传感器网络路由协议能有效地延长网络的生命周期，以及平衡网络中节点的能耗。

2. 背景知识

K中心算法是一种典型的聚类算法。K中心算法要求从n个节点构成的集合V中选取K个中心点，其余节点按欧氏距离的度量关联到离自己最近的中心点 [11] 。令S为K个中心点构成的集合，一个非中

心的普通节点 $i\in V/S$ 到S的距离定义为 $d\left(i,S\right)={\min }_{j\in S}d\left(i,j\right)$。该算法的目标是使 ${\max }_{i\in V}d\left(i,S\right)$ 达到最

小，这被证明是一个NP-hard的问题，在文献 [11] 中讨论了该问题的一个近似比为2的近似算法。

3. 基于K中心簇头的选举

由于LEACH簇头选取具有随机性，导致在数据传输的过程中，不可避免出现节点能耗分布不均衡，而在每轮根据节点的位置、剩余能量选取最佳的簇头分布是一个计算困难的问题。而PAGASIS存在链尾节点转发延迟过大的问题。

由于K中心选取问题考虑了极小化小内部节点到中心节点集的最大距离，本文基于K中心选取问题设计了WSN的簇头选取算法，以控制簇内节点到簇头的距离并节约能耗。把簇头视为待选取的中心节点。已有的K中心算法运行时需要固定的K值作为运行参数，这里的难点是如何选择合适的且动态变化的K值。本文根据LEACH对当选簇头的计数算法，生成一个二项分布的随机变量，实现可随网络运行，在每轮动态变化的K值。

3.1. 计算簇头选取的参数K

设传感器网络监测区域L大小为N × N平方米的正方形，均匀随机分布n个传感器节点，用V代表所有传感器节点组成的集合。整个网络的运行过程分为若干个周期 $T_1,\cdots ,T_i,\cdots$，每个周期 $T_i$ 又分为t轮

$T_i\left[1\right],\cdots ,T_i\left[t\right]$。在每轮簇头选取阶段，用变量K代表待选取的中心节点数。LEACH对当选簇头的计数的思路被借鉴用来生成随机变量K， $0\le p\le 1$ 为对应的系统概率参数。

在每个周期 $T_i$ 的第一轮的开始时刻，所有节点的G标志置为0。节点的G标志置为1表示该节点本周起内某轮当选过中心节点。

在每个周期 $T_i$ 的第j轮 $$ 的开始时刻，用 $N_j$ 表示此时所有G标志被置为0的节点数量。定义一个二项随机变量 $B\left[N_j,p_j\right]$，概率 $p_j$ 按LEACH协议的方式定义为：

$p_j=\frac{p}{1-p*\mathrm{mod}\left(j,\left[1/p\right]\right)}$ (1)

K取 $B\left[N_j,p_j\right]$ 在当前的随机实验所得的结果。

3.2. 生成中心节点集

K的值给定后，在每个周期 $T_i$ 的第j轮 $T_i\left[j\right]$ 根据已有K中心选取问题的近似算法(近似比为2) [11] 以K为参数设计了WSN的中心节点选取算法：

1) 给定参数K，用集合S来保存簇头，S初始化为空集，V初始化为当前G标志置为0的传感器节点集。节点 $i\in V$ 到集合S的距离定义为 $d\left(i,S\right)={\min }_{j\in S}d\left(i,j\right)$， $d\left(i,j\right)$ 为二维空间两点间的欧式空间距离。

2)随机选择一个点 $i\in V$， $S=S\cup \left\{i\right\},V=V\backslash \left\{i\right\}$

将节点i加入集合S，从集合V中去除节点i。

3) While $\left|S\right|<K$

$k=\underset{j\in V}{\arg \max }d\left(j,S\right)$

注：选取节点k为离当前集合S距离最远的非中心节点；

$S=S\cup \left\{k\right\},V=V\backslash \left\{k\right\}$

end

集合S中所有新当选的中心节点G标志置为1。

3.3. 关联簇头和数据转发

在生成了中心节点集合S后，普通节点按欧氏距离的度量关联到离自己最近的中心节点形成分簇结构。在数据向基站转发时，每个普通节点把数据转发到自己关联的中心节点，中心节点则把数据转发到基站。

4. 性能分析

4.1. 方案参数设置

本文在matlab平台上进行仿真实验，n = 100个同构的传感器节点随机分布在一个(0,0)至(100,100)的网络区域内，移动基站初始位置位于网络区域中心，坐标位置为(50,50)，节点的初始能量均为0.5 J。生成簇头的概率参数 $p=0.1$。具体能量参数设置如表1所示。

Table 1. Scheme parameter settings

表1. 方案参数设置

4.2. 能耗对比

图1展示了K-Center协议在第3000轮时所有传感器节点的能耗情况。由图1可知，在同一网络分布的条件下：

在第3000轮时，LEACH协议中的所有传感器节点剩余能量的最小值为0.2249，最大值为0.3583，极差为0.1334，平均值为0.2957，标准差为0.02822；

PEGASIS协议中的所有传感器节点剩余能量的最小值为0.2335，最大值为0.3643，极差为0.1309，平均值为0.2955，标准差为0.03029；

K-Center协议中的所有传感器节点剩余能量的最小值为0.2805，最大值为0.3106，极差为0.0301，平均值为0.2925，标准差为0.02801。

分析可知，K-Center协议相比LEACH和PEGASIS协议，传感器节点的能量消耗较少且更加平均稳定，有利于网络的长久运行。

Figure 1. Energy consumption comparison diagram

图1. 能耗对比图

4.3. 轮数对比

图2展示了K-Center协议的网络运行生命周期对比图。由图2可知，在同一网络分布的条件下：

LEACH协议的第一个退出节点轮数为1022，PEGASIS协议的第一个退出节点轮数为1057，K-Center协议的第一个退出节点轮数为1140，K-Center协议相比PEGASIS协议的生命周期延长了7.85%；

LEACH协议的最后一个退出节点轮数为1487，PEGASIS协议的最后一个退出节点轮数为1371，K-Center协议的最后一个退出节点轮数为3000，K-Center协议相比LEACH协议晚100.02%，K-Center协议相比PEGASIS协议晚118.81%。

分析可知，相比LEACH和PEGASIS协议，K-Center协议的第一个退出节点轮数和最后一个退出节点轮数都要好于LEACH和PEGASIS协议。因此，网络的生命周期得以延长。

Figure 2. Number of rounds for comparison

图2. 轮数对比图

5. 结论

本文分析了三种经典的WSN路由协议LEACH、三层LEACH和PEGASIS中使用的降低能耗的方法及优缺点。由于K中心选取问题考虑了极小化小内部节点到中心节点集的最大距离，本文基于K中心选取问题设计了WSN的簇头选取算法，以控制簇内节点到簇头的距离。本文根据LEACH对当选簇头的计数算法，生成在每轮自适应变化的K值。仿真结果表明，和LEACH协议、PAGASIS协议相比，提出的基于K中心的传感器网络路由协议能有效地延长网络的生命周期，以及平衡网络中节点的能耗。

基金项目

国家自然科学基金(61472343)，江苏省自然科学基金项目(BK20170512)，江苏省高校自然科学基金项目(17KJB413003)，扬州市自然科学基金项目(YZ2016113)项目。