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只要接收到其他节点对其所发请求的响应，就可以得到这个估值。 (责任编辑：南粤论文中心)转贴于南粤论文中心: http://www.nylw.net(南粤论文中心__代写代发论文_毕业论文带写_广州职称论文代发_广州论文网）