交通监控中基于模糊聚类的无线传感网MAC协议

摘要

本发明涉及一种交通监控中基于模糊聚类的无线传感网MAC协议，FC‑MAC协议采用TDMA和改进的CSMA/CA交替工作方式，即保证了普通周期数据的传递，又增强了突发数据的实时性。在竞争接入(CSMA/CA)阶段，提出模糊聚类分析的方法。根据因素向量聚类簇内节点，使节点突发数据具有不同的优先级，优先级高的突发数据更早接入信道完成传输。同时，根据该协议的时隙分配策略，提出一种基于分层随机延迟的方法，减少同一时段内竞争接入Sink节点的簇头数量，降低簇头节点之间因退避而产生的数据延迟。通过以上技术，FC‑MAC在突发数据时延减少的情况下，增大了网络吞吐量，并且对网络业务流量具有更好的适应性。

说明书

技术领域

本发明涉及一种应用于交通监控的无线传感网MAC协议，属于无线传感器网络技术领域。

背景技术

无线传感器网络(Wireless Sensor Network，WSN)是由大量分布在特定区域内的传感器节点组成，并且以无线通信的方式将感知到的数据传送到Sink节点。由于其独特的优势，WSN在国防军事、环境监控、工业技术、智能交通等方面获得了广泛的应用。在交通发达的当今社会，由于车辆快速增多，对交通监控的需求也不断地加大。无线传感器网络以其自身的特点，在交通监控中迅速地发展起来。而MAC协议是影响无线传感器网络性能的关键技术。所以，设计一种适合交通监控需求的MAC协议具有十分重要的意义。

目前，无线传感器网络MAC协议按节点接入信道的方式主要分为三类：基于竞争的MAC协议、基于调度的MAC协议和混合型MAC协议。在基于竞争的协议中，S-MAC采用固定占空比的周期休眠方式，侦听周期受通信负载的约束，在多个节点竞争时增大传输延迟。DSMAC虽然在S-MAC的基础上提出了减少睡眠时间、动态加倍占空比的思想，但周期睡眠造成的传输延迟仍十分显著。在基于调度的协议中，S-LMAC、EM-MAC都采用固定分配时隙的方法，无法自适应流量的变化。UM-MAC虽在固定时隙的基础上提出启发式的算法，以效用最大化决定节点的工作时隙，但无法满足突发数据的实时性要求。在混合型协议中，Z-MAC综合了TDMA和CSMA的优点，能够以较低代价获得高效的信道利用率，但在网络密度较大时，周期性地控制时隙会增大网络时延和能耗开销。AMPH在Z-MAC的基础上增加了QoS服务，但当普通数据包过多切换优先级时，会影响实时数据包的实时性。综上所述，这些协议都不适合交通监控的特殊环境。

发明内容

为了解决上述存在的技术问题，本发明提供一种应用于交通监控中，基于模糊聚类的无线传感网MAC协议实现方法。该协议采用TDMA和改进的CSMA/CA混合工作模式，并在CSMA/CA阶段引入模糊聚类的方法动态划分节点类别，根据每类的中心向量与样本中心向量的距离决定优先级，并分配不同的竞争参数，使优先级高的节点突发数据更早传输。同时，提出了一种分层随机延迟策略，降低簇头节点之间地竞争，提高了突发数据的实时性。

本发明是通过下述技术方案实现的：交通监控中基于模糊聚类的无线传感网MAC协议，其特征在于：采用TDMA和改进的CSMA/CA交替的工作方式划分时隙；在CSMA/CA阶段采用模糊聚类的方法动态划分优先级；簇头节点采用分层随机延迟策略降低碰撞概率；

具体步骤如下：

(1)执行本协议的部署工作：

(1.1)节点功能：簇内节点可对监测数据进行筛选分类，具体分为，突发数据和周期数据；筛选原则是：当外部数据的值大于门限值，进入突发数据队列；当外部数据小于门限值，则进入周期队列数据；

(1.2)时隙分配方案：

①时隙的分配以时隙块为基础单位，每个时隙块的大小由4个时隙组成；

②FC-MAC采用以复帧为周期的时间调度机制，复帧由若干TDMA帧与交换信息阶段组成；

③在TDMA帧中，每个节点分配三个时隙块，分别用作TDMA阶段、CSMA/CA阶段和SEND阶段；

(2)初始时刻，簇内节点量化分类因素，进而生成因素向量，发送到簇头节点；

(3)簇头节点接到簇内节点的因素向量后，对其进行模糊聚类；

(4)：对步骤(3)中产生的分类进行优先级的计算，

(5)：根据步骤(4)的优先级信息，为每类分配不同的竞争参数。

(6)：如果节点有突发数据，则在自己的TDMA阶段发送或所有CSMA/CA阶段竞争发送突发数据包；若节点没有突发数据，则在自己的TDMA阶段发送周期数据包，保证突发数据的实时性；

(7)：簇头节点对接收到的数据进行融合，并在SEND阶段把融合后的信息传送给Sink节点；采用分层随机延迟的策略，在网络初始阶段，把同一Sink节点下的簇头随机延迟0、1或2个时隙块，使簇头节点分成了不同的3个时段发送数据。

步骤(2)所述的簇内节点量化分类因素过程如下：

(2.1)对于传感器类型u_k，不同的传感器类型分配不同的权重，其中，光电测速传感器、地磁传感器的权重为H，压力传感器、加速度传感器的权重为M，温湿度传感器、光线光栅传感器的权重为L；其中H>M>L；

(2.2)对于传输距离d_k，通过接收信号强度测量其值；

(2.3)对于数据突变程度ε_k，可通过下面的公式求得：

${ϵ}_k=\delta \times {ϵ}_k^{*}+(1-\delta )\times {ϵ}_k^{\prime }$

${ϵ}_k^{\prime }=\zeta \times \frac{L\left(s\right)}{L\left(s\right)+L\left(c\right)}$

其中，ε_k为突变程度，为上一复帧该节点的突变程度，ε′为本次复帧内的突变程度，ζ为一个量化常数；在网络初始时刻，所有的节点量化常数相等，ε_k与的初值为0；L(s)、L(c)分别为节点队列中突发数据包和周期数据包的个数；为了更适合突发数据的长期变化趋势，把δ的值限定在0.5到1之间；

(2.4)对于节点剩余能量E_k，由能量消耗模型计算，如下：

E_k＝b(E_elec+E_fsd²)

其中，b为发送数据的比特数，E_elec为发射电路和接收电路的能耗，E_fs为传播消耗功率。

步骤(3)模糊聚类的过程如下：

(3.1)簇头节点收集簇内节点的因素向量，U＝{n₁,n₂,n₃,…,n_k}表示单个簇所覆盖的区域，簇内节点个数为k；每个节点在交换信息阶段发送u_k、d_k、ε_k、E_k等m个量化因素给簇头节点，则簇内节点i发送给簇头节点的向量为n_i＝(n_i1,n_i2,n_i3,…,n_im),i＝1,2,…,k，生成采集矩阵P；

$P=\left(\begin{array}{cccc}{n}_{11}& n_{12}& \mathrm{...}& n_{1m}\\ n_{21}& n_{22}& \mathrm{...}& n_{2m}\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ n_{k1}& n_{k2}& \mathrm{...}& n_{km}\end{array}\right)$

(3.2)对矩阵P做标准化处理，得到其模糊矩阵；公式如下，

其中

$r_{ij}=\left(\begin{array}{cc}1,& i=j\\ \frac{1}{M}\underset{k=1}{\overset{m}{\Sigma }}{n}_{ik}·n_{jk},& i\ne j\end{array}\right)$

经过处理得到的模糊矩阵为R；

$R=\left(\begin{array}{cccc}1& r_{12}& \mathrm{...}& r_{1k}\\ r_{21}& 1& \mathrm{...}& r_{2k}\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ r_{k1}& r_{k2}& \mathrm{...}& 1\end{array}\right)$

(3.3)采用Kruskal最大树算法进行聚类，得出最终的分类；分类的个数应适中，且与现实部署相关，根据交通监控的现实情况，分为三类为最佳；Kruskal的具体算法过程如下：

(3.3.1)假设节点形成连通网N＝(V，{E})，令最大树初始状态是只有节点而无边的非连通图T＝(V，{})，图中每个节点自成一个连通分量；

(3.3.2)在模糊相似矩阵的上三角中找出最大的数r_ij,i≠j；若该数依附的节点落在T中不同的连通分量上，则将此数作为边加入到T中，否则舍去，选择下一个最大的数；

(3.3.3)依次类推，直到T中所有节点都在同一个连通分量上为止，得出模糊相似矩阵R的最大树；

(3.3.4)选定不同的λ值，砍去最大树中低于λ的边，即得在λ水平上的分类。

步骤(4)优先级的计算，具体步骤如下：(4.1)求原始采集矩阵P的样本中心向量，计算公式如下：

${\bar{p}}_j=\frac{n_{1j}+n_{2j}+\mathrm{...}+n_{kj}}{k}=\frac{1}{k}\underset{i=1}{\overset{k}{\Sigma }}{n}_{ij}$

得到样本中心向量

(4.2)计算每一类的中心向量，如分类后的第θ类的中心向量为

(4.3)求每类的中心向量到样本中心向量的欧氏距离；离样本中心越近，类别的优先级越高；

$d_{\theta }=\sqrt{{({\bar{p}}_1^{\left(\theta \right)}-{\bar{p}}_1)}^2+{({\bar{p}}_2^{\left(\theta \right)}-{\bar{p}}_2)}^2+\mathrm{...}+{({\bar{p}}_m^{\left(\theta \right)}-{\bar{p}}_m)}^2}.$

步骤(5)为每类分配不同的竞争参数，其中包括仲裁帧间间隔AIFS，AIFS影响节点接入的先后顺序，不同的类别θ对应不同的值，如下：

AIFS_θ＝SIFS+C_θ×T_slot

其中，每个节点的短帧间间隔SIFS是个相等的常量，C_θ的值随着类别的优先级增大而减少，动态地区分不同类别接入的先后顺序。而节点的退避时间范围则是由竞争窗口CW和退避指数BE两个参数决定的。对于不同的分类θ，有不同的值和值，优先级越高的类别竞争窗口CW_θ的取值范围越小，使其有更高的概率竞争早期的时隙传输数据；

${\mathrm{CW}}_{\theta }=rand(0,2^{{\mathrm{BE}}_{\theta }}-1),{\mathrm{BE}}_{\theta }\in ({\mathrm{BE}}_{min}^{\theta },{\mathrm{BE}}_{\max }^{\theta })$

$T_{backoff}^{\theta }={\mathrm{CW}}_{\theta }\times T_{slot}.$

步骤(7)中所述分层随机延迟的策略具体如下：根据FC-MAC的时隙分配策略，网络初始时刻，Sink节点随机为每个簇头节点分配一个数值，数值在0,1,2中取；簇头节点接到这个数值之后，在网络同步开始时刻，延迟n个时隙块，这里的n就是Sink节点分配给簇头的数值；节点通过分层随机延迟策略，把同一Sink节点下的簇头分成了不同的3个时段发送数据，使以前α个簇头同时竞争的信道从物理上分隔开，每个时间段最好情况下有α/3个簇头竞争信道。

本发明的有益效果：本发明采用上述方案，充分考虑交通监控的特殊环境，提供了一种适用于保证突发数据实时性的MAC协议，该协议(FC-MAC)协议采用TDMA和改进的CSMA/CA两种工作模式，并在CSMA/CA阶段根据因素向量把簇内节点划分为不同的类别。同时，不同的类别赋予不同的优先级，以便高优先级类别的突发数据能够更早接入信道，完成数据传输。在簇头竞争接入Sink节点方面，采用分层随机延迟策略，以较低的代价降低簇头干扰，提高整体网络吞吐量。本发明所提供的MAC协议具有较高的网络吞吐量，并且有利于突发数据的传送，整体设计使突发数据时延较小，适用于交通监控系统。

附图说明

图1是网络部署示意图。

图2是节点内部队列结构图

图3是FC-MAC复帧结构图。

图4是各阶段工作关系图。

图5是簇间分层结构图。

图6是物理信道分割示意图。

具体实施方式

下面结合附图对本发明进一步说明。在十字路口处，由于上下班高峰期车流量大，阴雨雾霾天能见度低等原因，经常会发生交通事故或拥堵现象。把无线传感器节点部署在十字路口处，实时地监控道路信息对交管部门的管理起到了积极的作用。通过无线传感器节点采集各类信息发送给簇头节点，并经其汇聚信息后再发送给Sink节点，使管理者能够随时掌握路面信息，及时应对各种突发事件。

本发明的技术方案是将不同类型的传感器节点部署在十字路口处，组成一个无线传感器网络。其网络部署，如图1所示。在图1中，采用固定簇的方式，簇头节点使用特殊供电的形式部署在道路中央的隔离带、绿化带上，如图中实心节点。不同类型的簇内节点部署在簇头节点的周围，如图中空心节点。Sink节点固定在道路旁的路灯、红绿灯上。所有簇头节点和Sink节点均采用单跳通信结构。节点对监测到的外部数据进行分类，如图2所示。当外部数据的值大于门限值时，进入突发数据队列；当外部数据的值小于门限值时，则进入周期数据队列。

本发明采用TDMA和改进的CSMA/CA交替工作的模式，其时隙的分配以时隙块为基础单位，每个时隙块的大小由4个时隙组成。FC-MAC采用以复帧为周期的时间调度机制，复帧由若干TDMA帧与交换信息阶段组成。在TDMA帧中，每个节点分配三个时隙块，分别用作TDMA阶段、CSMA/CA阶段和SEND阶段。如图3所示。

交换信息阶段位于每个复帧的起始处，主要用于簇内节点向簇头节点发送因素向量，簇头完成CSMA/CA阶段优先级的计算，并把优先级信息反馈给簇内节点；TDMA阶段分配给固定的节点，用于传输普通周期数据；CSMA/CA阶段预留给有突发数据的节点竞争接入簇头；SEND阶段则负责把数据交付给Sink节点。

各阶段工作关系，如图4所示。整个网络的运行步骤如下：

步骤1：初始时刻，簇内节点量化分类因素，进而生成因素向量，发送到簇头节点。具体量化步骤如下：

(1)对于传感器类型u_k，不同的传感器类型分配不同的权重，具体如表所示。其中H>M>L。

(2)对于传输距离d_k，会影响到传输代价，可通过接收信号强度测量其值。

(3)对于数据突变程度ε_k，可通过下面的公式求得：

${ϵ}_k=\delta \times {ϵ}_k^{*}+(1-\delta )\times {ϵ}_k^{\prime }$

${ϵ}_k^{\prime }=\zeta \times \frac{L\left(s\right)}{L\left(s\right)+L\left(c\right)}$

其中，ε_k为突变程度，为上一复帧该节点的突变程度，ε′为本次复帧内的突变程度，ζ为一个量化常数。在网络初始时刻，所有的节点量化常数相等，ε_k与的初值为0。L(s)、L(c)分别为节点队列中突发数据包和周期数据包的个数。为了更适合突发数据的长期变化趋势，把δ的值限定在0.5到1之间。

(4)对于节点剩余能量E_k，由能量消耗模型计算，如下：

E_k＝b(E_elec+E_fsd²)

其中，b为发送数据的比特数，E_elec为发射电路和接收电路的能耗，E_fs为传播消耗功率。

步骤2：簇头节点接到簇内节点的因素向量后，对其进行模糊聚类。设U＝{n₁,n₂,n₃,…,n_k}表示单个簇所覆盖的区域，簇内节点个数为k。每个簇内节点发送m个量化因素到簇头节点进行聚类，具体聚类过程如下：

(1)簇头节点收集簇内节点的因素向量，生成采集矩阵P。

$P=\left(\begin{array}{cccc}{n}_{11}& n_{12}& \mathrm{...}& n_{1m}\\ n_{21}& n_{22}& \mathrm{...}& n_{2m}\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ n_{k1}& n_{k2}& \mathrm{...}& n_{km}\end{array}\right)$

(2)对矩阵P做标准化处理，得到其模糊矩阵。公式如下，其中

$r_{ij}=\left(\begin{array}{cc}1,& i=j\\ \frac{1}{M}\underset{k=1}{\overset{m}{\Sigma }}{n}_{ik}·n_{jk},& i\ne j\end{array}\right)$

经过处理得到的模糊矩阵为R。

$R=\left(\begin{array}{cccc}1& r_{12}& \mathrm{...}& r_{1k}\\ r_{21}& 1& \mathrm{...}& r_{2k}\\ .& .& & .\\ .& .& & .\\ .& .& & .\\ r_{k1}& r_{k2}& \mathrm{...}& 1\end{array}\right)$

(3)采用Kruskal最大树算法进行聚类，得出最终的分类。分类的个数应适中，且与现实部署相关，根据交通监控的现实情况，分为三类为最佳。Kruskal的具体算法过程如下：

3.1假设节点形成连通网N＝(V，{E})，令最大树初始状态是只有节点而无边的非连通图T＝(V，{})，图中每个节点自成一个连通分量。

3.2在模糊相似矩阵的上三角中找出最大的数r_ij,i≠j。若该数依附的节点落在T中不同的连通分量上，则将此数作为边加入到T中，否则舍去，选择下一个最大的数。

3.3依次类推，直到T中所有节点都在同一个连通分量上为止，得出模糊相似矩阵R的最大树。

3.4选定不同的λ值，砍去最大树中低于λ的边，即得在λ水平上的分类。

步骤3：对步骤2中产生的分类进行优先级的计算，具体步骤如下：

(1)求原始采集矩阵P的样本中心向量，计算公式如下：

${\bar{p}}_j=\frac{n_{1j}+n_{2j}+\mathrm{...}+n_{kj}}{k}=\frac{1}{k}\underset{i=1}{\overset{k}{\Sigma }}{n}_{ij}$得到样本中心向量

(2)计算每一类的中心向量，如第θ类的中心向量为

(3)求每类的中心向量到样本中心向量的欧氏距离。离样本中心越近，类别的优先级越高。

$d_{\theta }=\sqrt{{({\bar{p}}_1^{\left(\theta \right)}-{\bar{p}}_1)}^2+{({\bar{p}}_2^{\left(\theta \right)}-{\bar{p}}_2)}^2+\mathrm{...}+{({\bar{p}}_m^{\left(\theta \right)}-{\bar{p}}_m)}^2}$

步骤4：根据步骤3的优先级信息，为每类分配不同的竞争参数。其中包括仲裁帧间间隔(Arbitration Inter-frame Spacing，AIFS)，AIFS影响节点接入的先后顺序，不同的类别对应不同的值，如下：

AIFS_θ＝SIFS+C_θ×T_slot

其中，每个节点的短帧间间隔(Short Inter-frame Spacing，SIFS)是个相等的常量，C_θ的值随着类别的优先级增大而减少，动态地区分不同类别接入的先后顺序。而节点的退避时间范围则是由竞争窗口(Contention>θ的取值范围越小，使其有更高的概率竞争早期的时隙传输数据。

${\mathrm{CW}}_{\theta }=rand(0,2^{{\mathrm{BE}}_{\theta }}-1),{\mathrm{BE}}_{\theta }\in ({\mathrm{BE}}_{min}^{\theta },{\mathrm{BE}}_{\max }^{\theta })$

$T_{backoff}^{\theta }={\mathrm{CW}}_{\theta }\times T_{slot}$

步骤5：如果节点有突发数据，则在自己的TDMA阶段发送或所有CSMA/CA阶段竞争发送突发数据包；若节点没有突发数据，则在自己的TDMA阶段发送周期数据包，从而保证了突发数据的实时性；

步骤6：簇头节点对接收到的数据进行融合，并在SEND阶段把融合后的信息传送给Sink节点。由于簇头节点采用竞争的方式接入Sink节点，为了降低簇头间的竞争接入，采用分层随机延迟的策略，具体如下所述：

(1)根据FC-MAC的时隙分配策略，网络初始时刻，Sink节点随机为每个簇头节点分配一个数值，数值在0,1,2中取。

(2)簇头节点接到这个数值之后，在网络同步开始时刻，延迟n个时隙块，这里的n就是Sink节点分配给簇头的数值。如图5所示。

节点通过分层随机延迟策略，把同一Sink节点下的簇头分成了不同的3个时段发送数据，使以前α个簇头同时竞争的信道从物理上分隔开，每个时间段最好情况下有α/3个簇头竞争信道，如图6所示。