基于DRAND算法的漏斗.MAC协议.doc

基于DRAND算法的漏斗.MAC协议
摘要:针对漏斗.mac协议的不足，给出一种分布式时隙分配（drand）算法改进方案。在基于集中式时分多址（tdma）调度算法的漏斗.mac协议基础上引入分布式时隙分配方案，保证节点两跳范围内的时隙没有重叠，从而能最大限度地避免数据干扰和冲突。ns.2仿真表明，改进的协议能进一步减少系统能量消耗，维持较高的信道利用率。
关键词:漏斗.mac；分布式时隙分配算法；时分多址；分布式；ns.2
funneling.mac protocol based on drand algorithmzhu xiu.li*, li ying.jie
school of computer science and technology, zhoukou normal university, zhoukou henan 466099, china
abstract:
aiming at the disadvantage of funnelinf.mac protocol,this paper gave an improved proposal of drand algorithm.based on centralized tdma scheduling algorithm of funneling. mac protocol,it introduced the drand scheme,which guaranteed nodes have not overlap within the time slots in two.hop range,so it could avoid on interference and collision as possible.ns.2 simulation results show that improved protocol can effectively reduce system power consumption,and maintain higher channel utilization.
concerning the disadvantage of funneling.mac protocol, this paper gave an improved proposal of drand algorithm. based on the centralized time division multiple access (tdma) scheduling algorithm of funneling.mac protocol, it introduced the drand scheme, which guaranteed nodes did not overlap within the time slots in two.hop range, so it could greatly avoid interference and collision. the ns.2 simulation results show that the improved protocol can effectively reduce system power consumption, and maintain higher channel utilization.
key words:
funneling.mac; distributed randomized algorithm; time division multiple access (tdma); distributed; ns.2
0引言
无线传感器网络(wireless sensor network,wsn)［1-2］是由部署在所要监测区域内大量体积小、成本低，且具有数据采集、数据处理和数据无线收发能力的传感器节点组成。节点无线收发模块是最大的耗能部件，而mac协议［3］直接控制无线收发模块，对节点能耗有重要影响。因此，设计有效的mac协议，在传感器节点之间分配有限的无线通信资源来构建网络的底层基础结构具有重要意义和现实价值。
根据不同的实际应用，研究人员从不同角度出发提出了多种mac协议。根据信道接入方式的不同，主要有基于竞争(s.mac［4］)方式、基于调度时分多址(time division multiple access，tdma)联接方式［5］和混合型方式［6］(z.mac)。ahn等根据传感器网络汇聚sink节点附近数据流量大引起的
冲突、串音和丢包等问题，研究提出了漏斗.mac(funneling.mac)协议［7-8］。本文在分析
漏斗.mac协议原理、运行机制、优势以及存在问题的基础上，从节省网络能量消耗出发，针对协议sink节点附近的数据收发冲突和串音等问题引入分布式时隙分配算法［9-12］(drand)进行改进，同时借助仿真软件ns.2［13-15］对改进前后的协议进行对比仿真并分析之。
1漏斗.mac协议
无线传感器网络多跳聚播通信容易造成sink节点附近数据分组产生冲突、拥塞和丢包，称其为“漏斗效应”[7](funneling effect)。漏斗.mac协议(funneling.mac)是一种基于csma与tdma相结合的mac协议，该协议在全网范围内采用csma/ca方式进行数据传输，在sink节点附近则采用csma和tdma混合的信道访问方式。这样sink节点附近的节点有更多机会使用基于调度的方式来访问信道传输数据，很好地解决了汇聚节点附近区域数据流量大引起的冲突和丢包问题。漏斗.mac协议以csma方式为主，sink节点周期性地广播信标(beacon)，只有接受到信标的节点才使用csma和tdma相混合的方式交替访问信道，一个csma帧和tdma帧组合成为一个超帧。csma帧用于发送节点本身产生的数据以及其他控制信息，tdma帧包含若干个时隙，用于调度转发其他节点路由过来的数据，sink节点逐渐增加广播功率级别，直到网络达到饱和为止。funneling.mac协议对系统时钟要求不高，具有较高的信道利用率。图1所示为一个典型的funneling.mac协议场景图。
无线传感器网络mac协议设计的目的是在满足应用要求的前提下，尽量节省使用节点的能量，使数据快速有效地传输。因此，本文在漏斗.mac协议的基础上，针对协议sink节点附近数据收发使用集中式tdma调度算法容易产生冲突和干扰的不足引入分布式时隙分配(drand)算法进行改进。
2drand
2.1基本原理
分布式随机时隙分配算法(drand)是无线ad.hoc网络分布式、强壮和可扩展的算法，是集中式tdma算法的全分布式版本。节点开始启动时，首先执行一个简单的相邻节点发现和寻找协议，该算法周期性地给其一跳范围内邻居节点广播ping消息，每个节点从ping消息收集其一跳范围内邻居节点的信息，这样就组成其两跳相邻节点的列表信息，两跳相邻节点列表作为时隙分配算法的输入。drand算法对两跳距离内的节点进行着色，使两跳距离内各个节点得到不同的颜色。drand算法能够对任意拓扑图进行时隙分配，按照循环方式工作。drand算法还要求每个节点维护其一跳相邻区域的状态，不要求每个节点同步到每轮的时间边界上。这样能够高效地自适应本地拓扑结构变化，而不会产生传输时间安排的全网开销。

2.2算法设计与实现
在设计drand算法时，假定网络是广播方式且算法循环运行，每轮的持续时间根据网络延时动态调整，每个节点维护4种状态：空闲(idle)、请求(request)、同意(grant)和释放(release)。图2所示为drand算法的状态转换图，在箭头始端标注的是进行状态转移的条件，在箭头末端标注的是转移到新状态前的操作。
分区
图片图2drand状态转换图开始时，假设某个节点a处于空闲状态，a开始投硬币，出现正面、反面的概率是相等的，都为1/2。如果节点得到硬币正面，则抽彩，抽彩有一定的成功概率。节点若是中彩，则与其邻居节点交换消息，协商选择一个时隙，更准确地说：每个节点j维护一个估值cj，即对其一跳相邻节点和两跳相邻节点中还没有确定时隙的那些节点估值。如果从最近一次抽彩以来所经历的时间大于ta，则a抽彩，且将赢取概率设为pa=1/k，其中将k设为cj的最大值，对a的一跳相邻节点和两跳相邻节点中的所有j。
设i为a迄今为止抽彩的次数，则称a处在第i轮中，如果a中彩，那么a将转移到request状态，给其一跳内相邻节点广播一条requesti(请求)消息。若a没有中彩，则将继续保持在idle状态。设ta=3da，其中da为a对其消息单向传输延时最大值的估值，即a只要接收到其他节点对其所发请求的响应，就可以得到这个估值。
由以上分析可知，当节点a接收到其所有一跳范围内相邻节点对其所发的requesti消息或所回送的granti消息后，节点a就决定自己的时隙为本轮之前其两跳范围内相邻节点还未占用的时隙中时隙号最小的那个时隙。然后节点a转移到release状态，给其一跳范围内相邻节点广播一条releasei消息，releasei包含节点a所选定的时隙。节点a的一跳范围内相邻节点接收到releasei消息后，有两种处理情况：若该相邻节点还没有确定自己的时隙，则转移到idle状态；若该相邻节点已经确定了自己的时隙，则转移到release状态，然后将该releasei消息重新广播给自己的一跳相邻节点，此时的releasei消息称为two.hop.releasei(两跳释放)消息。节点接收到two.hop.releasei消息后就能够估计k值大小。图3为drand算法的具体实现流程。drand算法能保证节点两跳范围内的时隙没有重叠，数据收发不会产生干扰和冲突。同时drand算法还具有良好的适应性和鲁棒性，因为它不依赖整个网络的拓扑结构，只是根据两跳范围内的节点数来分配时隙。用drand算法实现无线传感器网络mac协议时隙分配，由于是相邻节点竞争公共信道的访问，所以节点的消息传输延时可能受其相邻区域大小的限制，设节点j在第k个循环获得一个时隙的概率期望值为pr(jleave,t)。
3实验仿真与结果分析
为了评估协议的各项性能，使用网络仿真软件ns.2进行仿真分析，采用改进协议(new.mac)和漏斗.mac协议(funneling.mac)对比仿真的形式来比较和分析为了验证改进协议的正确性和各项性能指标，本文采用图1所示的仿真拓扑结构：20个普通传感器节点和一个sink节点0。普通节点随机部署，节点发送的数据通过其他节点的路由转发最后都汇聚至sink节点0。传感器节点随机部署在1000m×1000m的区域，节点的场景部署和数据流配置采用ns2自带的setdest和cbrgen工具来进行设置，应用层采用不同间隔的cbr数据流，需要注意的是本文的仿真实验每个节点都是静止的，节点的工作频率为ism频段的914×106hz，路由协议采用表驱动路由协议(dsdv协议)，每次仿真时间为1000s。仿真初始参数设置如下：节点初试能量为100j；发送状态能量消耗pt=15μw；接受状态能量消耗pr=10μw；空闲状态能量消耗pi=5μw；睡眠状态能量消耗ps=1μw；唤醒节点能量消耗pw=3μw。图4此处原文图序有问题，需仔细核对修改是否正确】所示为节点两跳范围吞吐量对比情况。由于改进后的协议在sink节点附近使用drand算法，可以保证漏斗区域节点两跳范围的数据收发时隙没有重叠，因此，当网络发送节点增加时，drand算法可以为收据收发节点分配互不冲突的时隙，这是集中式tdma算法无法做到的，如图4所示，随着数据发送节点的增加，改进协议两跳范围吞吐量要大于原协议。
图5两跳范围丢包率图6所示为网络节点平均能量消耗对比情况。其计算方法是：网络中所有节点消耗的总能量，除以节点数。本文的改进协议由于引入drand算法，网络中各节点只在各自的时隙内收发正确的数据，极大地避免了干扰和数据冲突，从而能节省系统能量消耗。如图6所示，改进后的协议能量消耗要小于原协议，特别是在网络数据流量增大的时候。图片
图6网络节点平均能量消耗5结语
本文给出了一种改进的应用于无线传感器网络的漏斗.ma协议，在靠近sink节点的漏斗区域，通过引入drand算法，给两跳范围内节点分配不同的时隙，极大限度地避免了数据干扰和冲突，使数据快速有效地传输。仿真结果表明，在所有条件设定一致的情况下，改进后的协议能保持较高的系统吞吐量和信道利用率，延长网络使用寿命。
参考文献:
[1]
孙利民,建中,陈渝.无线传感器网络［m］.北京：电子工业出版社，2009:316.
[2]
任丰原，黄海宁，林闯.无线传感器网络［j］.软件学报，2003，14(7)：1282-1290.
[3]
蹇强，龚正虎，朱培栋，等.无线传感器网络mac协议研究进展［j］.软件学报，2008，19(2)：389-403.
[4]
ye w, heidemann j, estrin d. an energy.efficient mac protocol for wireless sensor networks[eb/ol]. [2011-04-01].http://www.isi.edu/～johnh/papers/ye02a.pdf.
[5]
arisha k a, youssef m a, younis m. energy.aware tdma.based mac for sensor networks ［eb/ol］.[2011-06-02].http://www.pitt.edu/～wrg/mc/seminartdma.pdf.
[6]
rhee i, warrier a, aia m, et al. z.mac: a hybrid mac for wireless sensor networks ［j］. ieee transactions on networking, 2008, 16(3): 511-524.