一种基于大规模网络分解和协调的WSNs MAC协议*

林钟楷，程良伦

（广东工业大学自动化学院控制网络与系统研究所，广东广州 510006）

0 引言

目前，大规模无线传感器网络（WSNs）的路由协议大多采用了树状拓扑结构［1］，通过分簇和Sink节点实现分层管理，以减少网络控制的复杂程度。针对这种结构，文献［2］中Lu G等人提出一种基于路径规划原则的DMAC协议，根据数据的传输路径来规划信道，引入交错的监听睡眠调度机制，保证数据在多跳路径上的连续传输。文献［3］中的Barroso A等人提出以簇为规划核心的混合型协议μ-MAC，该协议以Sink节点为核心，向上与其它Sink节点对信道实行竞争，向下对下层节点进行统计和分配，实现节点的有序接入。而文献［4］中，古连华等人对文献［3］做了改进，通过加入下层节点到Sink节点的数据通信预约机制，进一步提高了网络的自适应性。文献［5］则进一步对网络进行划分，引入了虚拟群的结构，提出了基于虚拟群的信道接入和休眠管理体制，强化了网络的管理，避免了冲突和时延。

上述协议在一定程度上能够解决大规模节点分布的网络中的能量和效率问题，但仅仅参考节点的自身资源，没有考虑到随着网络规模的扩大所带来的簇的规模扩大化和结构复杂化。当网络规模过大时容易带来簇与簇之间的相互牵扰，以及簇内节点过多带来的剧烈竞争问题。本文提出一种基于大规模网络分解和协调的自适应MAC协议（an adaptive MAC protocol based on decomposition and coordination of large-scale networks，ABDC-MAC），其主要思想是:按照网络层次和时间关联性，使用文献［6］提出的分解方法对树状拓扑结构进行串行和并行划分，同时引入网络结构、节点资源、通信时间等因子，采用文献［7］中提出的RBRS方法对节点参与网络竞争的概率进行调整。该协议实现了网络结构的优化，大大减少了复杂网络结构带来的能量和通信问题。

1 协议的提出

1.1 网络结构

假定存在如图1所示树状结构，同质节点随机分布在正方形区域中，基站（BS）的能量不受限制，节点周期性地遥感所有传感器的数据，并通过多对一的汇聚模式逐级由子节点向父节点传输，并最终汇集到Sink节点，再由Sink节点传递到基站。在这种树状结构中，只有父子关系的相邻节点存在业务转发，但临近节点的业务时间相关性较强。这种结构的父子节点数据关系与传统分群协议中成员与群首的业务模式类似。本文在树状结构与分群协议［5］的基础上，对网络进行进一步的细分，通过降低簇的规模实现网络的灵活性。

图1 树状拓扑网络结构Fig 1 Architecture Tree topology network

1.2 ABDC-MAC协议对网络的分解

本文提出的网络分解方法分为串行分解和并行分解［6］2种模式，其分解的最终目标是把网络分解为包含10～20个节点的子项目组，每个项目组有一个现实（通过串行分解）或者虚拟（通过并行分解）的父节点。首先，对网络使用串行分解，得到第一层的子节点群，然后对数量大于20的子节点群使用串行分解，得到第二层的子节点群，继续对未达到分解目标的节点群继续进行分解，直到达成分解目标为止。同时在每一层引入并行分解机制，对每一层的子节点数目进行限制。

1）串行分解

串行分解主要通过查找节点的传播路径来实现，按照网络的树状架构，各个节点的信息总是通过多对一的汇聚模式逐步向Sink节点和基站汇合，与汇聚节点相关的节点构成了一个子节点群，而汇聚节点本身则作为该群的父节点存在。串行分解就是k－1层汇聚节点对与其有数据关联关系的k层节点的划分，通过对k层节点上传数据的关联关系进行鉴别，区分出汇聚节点及其关联节点，并重新定义汇聚节点为k层节点，与汇聚节点关联的节点为其子节点k+1层。同时，对除了汇聚节点及其关联节点之外的独立节点暂时将其分在k层。串行分解后，会形成以k层汇聚节点为父节点的群和零散的独立节点。

2）并行分解

串行分解完成后，如果k层同时存在汇聚节点和独立节点，或者独立节点的个数超过分解目标，则对独立节点进行并行分解，其原则如下:

a.使得该集合中的所有节点与其它节点的活动没有时序关系;

b.若完成a步骤后，该集合中的节点数超过分解目标的，则对该集合进行切割，通过设置时间标志，将集合中的节点按照时间关系分割为2个集合;

c.若完成b步骤后，集合中的节点数仍超过分解目标，则继续执行b步骤;

d.对于每个集合，随机选择一个节点作为虚拟父节点，位于k层，而其余节点为子节点，位于k+1层。

同时，若汇聚节点与虚拟汇聚节点的数量超过分割目标，同样进行并行分解，其分解原则与独立节点的分解原则相同，但最后的虚拟父节点由k－1层的相关汇聚节点担任。

通过上述的串行和并行分解，网络的结构如图2所示。由于进行了基于路径和时间的分解，各个最小群组间的时序关系达到了最小关联，最大可能性地减小了群间通信的串扰。

图2 ABDC-MAC协议拓扑结构Fig 2 ABDC-MAC topology

1.3 ABDC-MAC协议的运行

本文提出的ABDC-MAC协议的运行分为两部分:建立阶段和运行阶段。在建立阶段，主要是对网络的分割、同步和初始化。而在运行阶段，主要是节点自身网络参数的主动调整与上传，使得整个网络参数得到调整，适应网络流量的动态变化。

1.3.1 建立阶段

建立阶段主要是分为2步:对大规模网络进行串行和并行分解，并建立节点的上下层节点信息表和处理节点同步问题，同时采集节点的初始信息。具体步骤如下:

1）网络分割

在网络的分割阶段:1）由Sink节点做一个长度为一个调度周期的开始信号广播，Sink节点下属的子节点收到开始信号后，将持续监听网络;2）每一层的汇聚节点使用嵌套点名法对其直属的子节点进行点名，得到回应后向其传递下一层的隶属节点信息和简单同步信息。当子节点的点名完成后，向上一级汇聚节点报告。嵌套点名法如图3所示;3）对于独立节点的虚拟父节点采取同样的方法，对于汇聚节点的虚拟父节点，则对其每一个子节点进行点名。

同时，节点上会建立上游信息表（表1）和下游信息表（表2），对上下游的节点进行登记和管理，主要用于休眠时间同步和网络参数计算。其中，R，T和NS为节点的资源负载参数、时延参数以及网络复杂度参数。

表1 上游信息表Tab 1 Present node’s info

表2 下游信息表Tab 2 Child node’s info

图3 使用嵌套点名法对节点进行分割Fig 3 Decomposition the network by roll-call method

2） 休眠时间同步和节点信息初始化

休眠时间的同步和节点信息初始化由该网络的父节点发起，父节点根据网络承载业务和时延要求设定休眠占空比，并选择休眠开始时间进行广播，其他节点接收后，根据上游信息表确定时候为父节点，若是，则在调度信息中加入，否则，丢弃。调度信息记录完成后，节点上传Rs，Ts，NSs和时钟参数，父节点接收后，反馈时钟漂移校正参数，并完成本次同步过程。

1.3.2 运行阶段

ABDC-MAC协议的运行模式如图4所示:

1）协议总体上采用竞争型架构，在每一层由父节点（包括虚拟父节点）竞争一定时长的信道使用权，父节点竞争到信道使用权后，将使用权划分为多个时长，由其子节点竞争。

2）父节点对信道的竞争原则与文献［8］的原则类似，但引入一个参数P（s）。该参数代表节点在信道竞争阶段选择接入信道的概率。该参数与父节点及其下属子节点的资源负载R，子节点与父节点的通信时长T和该节点群的网络复杂程度NS，以及竞争期时隙选择有关。同时需要指出的是，节点在上传数据的时候，还需将自己现在的Rs，Ts和NSs参数上传，作为上级节点的计算参考值。

3）子节点对信道的侦听采用跟随监听方式，即从顶层节点开始跟踪，若在一个竞争周期内检测到得到信道使用权的节点不是自己的上级节点的时候，会转入休眠节点直到下一个周期的到来;若为自己的上级节点，则会逐级跟踪，直至到达自己的额竞争周期为止。

4）对于底层节点，由于其数目较少（小于预订分解目标20），故采取轮询的方法，一次性采集20个节点的数据并在上层父节点整合上传。

5）若遇到路由协议更换Sink节点的情况，则只对出现变动的分组进行重新分解，以减少由组织网络带来的时间和能量损耗。

图4 ABDC-MAC协议的运行Fig 4 Operation of ABDC-MAC protocal

2 仿真与实验分析

本文提出的ABDC-MAC协议在NS-2平台进行仿真，为了对比评价，同时实现了ABDC-MAC和S-MAC协议。测试的性能指标有:ABDC-MAC的组网效率，ABDC-MAC协议与S-MAC协议的节能效率和网络延时对比。网络的主要设定参数如表3所示。

表3 仿真参数Tab 3 Network simulation parameter

表4列出了ABDC-MAC协议的组网效率，可以看出:当网络初始化或者其构造发生较大的变动的时候，ABDCMAC协议需要较长的一段时间进行组网;而当由于路由更换Sink节点等原因发生小范围的变化时，ABDC-MAC协议可以较快地调整好网络。

表4 组网效率Tab 4 Networking efficiency

由图5可以看出:在运行中，由于节点只需侦听与自己有关的上层节点是否得到网络，而不必每个时段都进行侦听，ABDC-MAC协议运行阶段的能耗远远低于一般竞争型协议。不仅很好地弥补了组网阶段的能耗，在总体能耗上也有很大降低。

图5 节点平均能耗Fig 5 Average power consumption of each node

由图6分别列出了ABDC-MAC协议对比S-MAC协议的网络延时。可以看出:虽然增加网络复杂度带来了一定的网络延时，但由于大规模网络下组网更加合理，带来的碰撞和重传次数的减少，节点的延时大致与S-MAC协议相近，在数据量大的情况下甚至优于S-MAC协议。

图6 节点时延性能实验Fig 6 Time delay property experiment of nodes

3 结论

本文提出一种基于大规模网络分解和协调的自适应MAC协议，该协议通过对网络的二次重构和节点的优先级计算实现大规模网络的有序化。仿真结果表明:在大规模组网的情况下，该协议总体能耗低、传达率高，且具有一定的自适应性，同时网络时延并没有因为分层而增加。该协议对大规模无线传感器网络有良好的适用性。

［1］Krishnamachari B，Estrin D，wicker S.The impact of data aggregation in wireless sensor networks［C］//The 22nd International Conference on Distributed Computing Systems Workshops，Vienna，Austria，2002:575 －578.

［2］Lu G，Krishnamachari B，Raghavendra C S.An adaptive energyefficient and low-latency MAC for data gathering in wireless sensor networks［J］.IEEE IPDPS，2004，224:26 －30.

［3］Barroso A，Roedig U，Sreenan C.μ-MAC:An energy-efficient medium access control for wireless sensor networks［C］//Proc of European Workshop on Wireless Sensor Networks，2005:

［4］古连华，程良伦.A μ-MAC:一种自适应的无线传感器网络MAC 协议［J］.自动化学报，2010，1:54－59.

［5］Li J，Lazarou G.A bit-map-assisted energy efficient MAC scheme for wireless sensor networks［C］//The 3rd Int’l Symp on Information Processing in Sensor Networks，IPSN 04，New York，2004:55－60.

［6］程 序，吴 澄.大规模项目调度问题的分解和协调优化方法［J］.清华大学学报:自然科学版，2009，49:40 －43.

［7］Herrolen W，Reyck B D，Demeulemeester E.Resource constrained project scheduling:A survey of recent develop-ments［J］.Computers＆ Operations Research，1998，25（4）:279 －302.

［8］Ye W，Heidemann J，Estrin D.An energy-efficient MAC protocol for wireless sensor networks［C］//Proc 21st Int’l Annual Joint Conf on Computer and Communications Societies，IEEE，New York，2002.