无线传感器网络延时测量数据的信息熵与不确定性
2011-03-16王婕
王 婕
(中北大学电子与计算机科学技术学院,太原 030051)
0 引言
无线传感器网(wireless senser network,WSN)由大量传感器节点组成,传感器节点负责对监测区域内的某些特定数据进行采集,并通过无线通信方式形成的一个多跳自组织网络,是一种新的分布式系统。WSN能够检测、监控和处理现实生活中的很多问题,在军事上实现战场的实时监控,对森林火灾和动物栖息地的监控口,在医学上监护病人的病情等都有很好的应用。
WSN是一个以数据为中心的网络,通常具有数据融合功能的网关节点会收集普通节点发送给它的原始信息,然后对信息进行分析和处理。为了保持节点本地时间的一致性,必须调整本地时钟。时间同步协议为精确地调整本地时钟提供了依据。
目前许多科学家和工程技术人员对无线传感器网络时钟同步进行研究,并取得了很好的成果,概括起来大致分为3类[1]:
(1)基于发送者和接收者的单向机制
在这个机制中,发送节点广播含有节点本地时间的分组,广播范围内的节点测量分组的传输延迟,再根据接收到的分组中包含的时间,即可得到与发送者间的偏差,进而同步。典型的算法如FTSP算法和由伯克利英特尔研究实验室提出的延时测量时间同步协议(DMTS)算法。
(2)基于发送者和接收者的双向机制
这种机制类似于Internet上的NTP协议,典型的算法如TPSN算法。
(3)基于接收者和接收者的机制
这种机制利用无线数据链路层的广播信道特性,引入第三方节点广播一个参考分组,在广播域内的接收节点收到这个分组后,通过比较各自接收到消息的本地时间,即可得到接收者间的偏差,如RBS算法。
本文在 DMTS算法基础上结合时延的指数分布特性,建立了相应的模型,然后又用最大熵方法的网络延迟概率密度函数,结合不确定度对其函数进行评价,使得根据最大熵原理计算的概率密度函数更接近于真实值。
1 传感器网络时钟同步原理
传感器网络中节点的本地时钟依靠对自身晶振中断计数实现,晶振的频率误差和初始计时时刻不同,使得节点之间的本地时钟不同步。如果能估算出本地时钟与物理时钟的关系或者本地时钟之间的关系,就可以构造对应的逻辑时钟以达成同步。
节点时钟通常用晶体振荡器脉冲来度量,所以任一节点i在物理时刻t的本地时钟读数可表示为[2]:
其中t为真实物理世界的时间;f0为节点晶振的标称频率;f(t)为晶振的实际频率;t0代表开始计时的时刻;Ci(t0)为计时开始t0的时钟读数。
对任何两个时钟A和B,分别用CA(t)和CB(t)来表示它们在t时刻的时间值,那么[3]:
偏移可表示为:CA(t)—CB(t)
2 DMTS算法
然而我们用公式 t0+nΔ t + (t2− t1)调整时钟是有误差的,而这个时延误差一般符合指数分布。DMTS协议的精确性要取决于延时测量的精确度,它是一种灵活轻量级能量,利用高效的时钟同步机制可应用于时钟同步要求不太高的无线传感网络中,该机制还能够更好地支持与外部时钟源及多跳点的同步。
3 模型的建立
由DMTS算法,不难得到:
化简得:
图1 DMTS时钟同步算法
其中 表示接收方与发送方的时钟偏移量,nΔ t表示传输时延的固定部分,X表示时延的可变部分。
文献[5-7]不但证明了指数分布对随机时延是正确的,而且还提出了几种估计时钟偏移量的算法。这都证明了假设随机延迟服从指数分布是正确的。
令Y= (t1−t0), z = n Δ t +,X=Y−z,因为X服从均值为 的指数分布,它的密度函数为:
最大熵原理[1-2]是在1957年由E.T.Jaynes提出的,其主要思想是,在提供数据有限或概率空间不完备的情况下,估计概率分布或确定未知参数,应充分利用现有信息,选择出具有信息熵最大的那一种概率分布,作为估计或预测的结果。
运用最大熵原理附加其约束条件和属性条件:
基于最大熵原理,对信息熵函数附加的(3)和(4)约束条件和属性条件,借助拉格朗日乘子法,推导出对数正态分布随机变量所服从的最大熵分布公式。
M对 f ( x)求偏导,并使其等于0得:
所以满足上述3个约束条件的最大熵分布的概率密度函数为:
4 时钟同步测量结果的不确定性分析
报文传输延迟的不确定性是无线传感器网络时钟同步的挑战之一。 一方面传输延迟比要求的时间同步允许的误差大得多,另一方面它极易受到处理器负载、网络负载等因素的影响。通常,报文的传输延迟可分为:发送延迟、访问时间延迟、传输时间延迟、传播时间延迟、接收时间延迟、接收处理时间延迟。传输延迟的不确定性严重影响了同步精度,因此需要对传输延迟仔细的测量、分析和补偿才能设计出高精度的时间同步协议。
我们用仿真实验的方法再来验证模型,根据DMTS算法对无线传感器时钟的测量,为方便计算,在确定的[0ms,4ms]区间内,取出300个样本如图2所示,经过计算得0= 0 . 3 4 1 和1= − 1 . 4 2 8 ,最大熵分布的概率密度函数分布图如图3所示。
图2 原始数据
图3 概率密度函数分布图
根据不确定度的评定如下[10]:
用本文采用的方法所估计的测量结果及其不确定度,比较接近于指数分布的被测量理论真值0.7和理论不确定度0.7,符合模型的结论。
5 结束语
本文主要利用时钟偏移量误差的规律性,提出基于指数时延的无线传感器网络时钟同步估计算法。基于发送者同步模型,在DMTS算法的基础上引入指数时延得到的。针对无线传感器网络延迟测量数据处理中掺杂的主观因素不能准确反映客观现实的问题,采用最大熵方法,根据测量数据求取被测量的概率分布,进而结合不确定度对此概率分布在约束条件下进行估计和评价。
[1] 杨博,廖明宏.基于统计的无线传感器网络时钟同步协议[J].哈尔滨工业大学学报,2007,39(1):98-100.
[2] 陈桥.无线传感器网络的时钟同步算法的研究与应用[D].西安:西安理工大学,2010:11-12.
[3] 刘晓璐,周书民.无线传感器网时间同步算法的比较[J].江西科学,2010,28(4):521-523.
[4] 程丽娟.无线传感器网络时间同步算法研究[D].西安:西北工业大学,2007:26-27.
[5] Jeske DR.On maximum-likelihood estimation of clock offset[J].IEEE Transactions on Communications,2005,53(1):53-54.
[6] Qasim M Chaudhari,Erchin Serpedin.Clock estimation for longterm synchronization in wireless sensor networks with exponential delays[J].EURASIP Journal on Advances in Signal Prossiong,2008,(1):1-6.
[7] 田贤忠,龚婷.基于指数时延的无线传感器网络时钟同步估计[J].小型微型计算机系 统,2009,11:2186-2188.
[8] 田宝玉,杨洁.信息论基础[M].北京:人民邮电出版社,2008:255-273.
[9] 凌能祥.信息熵在复杂性供应链协调中的应用[D].合肥:合肥工业大学,2007:20-24.
[10] 程亮,童玲.最大熵原理在测量数据处理中的应用[J].电子测量与仪器学报,2009,23(1):47-50.