法律状态公告日
法律状态信息
法律状态
2018-11-06
未缴年费专利权终止 IPC(主分类):H04W40/04 授权公告日:20141105 终止日期:20171116 申请日:20121116
专利权的终止
2014-11-05
授权
授权
2013-04-03
实质审查的生效 IPC(主分类):H04W40/04 申请日:20121116
实质审查的生效
2013-02-27
公开
公开
技术领域
本发明涉及一种多对一分簇无线传感器网络环境下节点睡眠调度方法,属于无线传感器 网络技术领域。
背景技术
无线传感器网络是一种无基础设施的无线网络,能够实时监测、感知和采集网络分布区 域内的各种环境或监测对象的信息,并对这些数据进行处理,最后将信息通过自组织网络传 送给用户。
传感器网络节点数量庞大,而且往往分布在环境恶劣的地区,不方便随时充电或更换电 池,但是网络又要求具有较长的寿命,因此,如何合理利用传感器节点能量,设计低能耗的 网络协议,延长传感器网络寿命,是无线传感器网络研究的一个重要问题。
无线传感器节点的无线传输可以分为空闲侦听、接收数据、发送数据和睡眠四种状态。 一般情况下空闲侦听和传输时消耗的功率差别不大,是睡眠状态的103~104倍。由于网络环 境所产生数据的时间并不固定,很多节点会长期处于空闲侦听的状态,消耗了大量的能量。
现有的睡眠调度算法中,核心思想都是减少节点处于空闲侦听状态的时间,让节点尽可 能多的处于睡眠状态,但有两方面缺陷:(1)部分睡眠调度算法中,只是单纯的将完成数据 发送与接收工作的节点从空闲侦听状态切换到睡眠状态,虽然这样可以最大程度的保证节点 睡眠时间,但是,频繁的状态切换,也会消耗很多能量,总能耗不一定降低,而且,频繁的 切换状态,使节点相关工作器件频繁关闭、启动,也会一定程度上降低节点寿命;(2)有的 睡眠调度算法中,也考虑到上述问题,采取了根据数据传输情况,减小状态切换次数的方式, 降低状态转换部分的能耗,但这样的规划,不能最大程度的减少空闲侦听,根据规划,有些 节点处于空闲侦听时将不会切换到睡眠状态。
发明内容
本发明的目的是为了解决上述问题,提出一种多对一分簇无线传感器网络环境下节点睡 眠调度方法,本发明在保证网络数据传输的前提下,将处于空闲侦听状态的节点休眠,节省 大量的能量消耗,通过构建基于能耗的跨层优化模型,得到簇头节点睡眠调度方法,降低网 络能耗,保证骨干网络中各个节点能耗的均匀分布,延长网络寿命。
一种多对一分簇无线传感器网络环境下节点睡眠调度方法,包括以下几个步骤:
步骤1:进行网络初始化;
步骤2、根据路由查找算法,获取无线传感器网络的数据聚合树,得到路由矩阵R;
步骤3、确定簇头节点的周期运行方法,构建基于能耗的跨层优化模型,获取每一个簇 头节点的睡眠调度方法;
步骤4、无线传感器网络根据节点睡眠调度方法,每一个节点根据该节点的睡眠调度方 法开始运行,向父节点上传数据;
步骤5、当每个节点在向父节点发送数据之后,进入睡眠状态之前,根据当前无线传感 器网络状态,获取基于能耗的跨层优化模型的输入,采用步骤3中(2)构建的基于能耗的 跨层优化模型,获取该节点下一次的节点睡眠调度方法,并将该方法告知该节点的父节点和 兄弟节点;
步骤6、无线传感器网络判断簇头节点的能量是否耗尽,如果是,转入步骤7,否则, 返回步骤4;
步骤7、如果骨干网络中有簇头节点能量耗尽,采用路由查找算法,判断当前剩余的骨 干网络节点是否能够重新构建数据聚合树,若能够重新构建数据聚合树,则返回步骤2,否 则骨干网络能量耗尽,无线传感器网络终止运行。
本发明的优点在于:
(1)本发明设计了节能的簇头节点的周期运行方法,将节点睡眠调度算法融入到骨干网 络的TDMA(Time Division Multiple Access,时分多址)规划中。根据所设计的方法, 可以保证在一个周期内,每个节点只唤醒一次,唤醒后完成收集簇内数据、收集子节点数据、 发送数据等工作,更新规划后进入睡眠状态。这样,一方面可以最大程度的减少节点状态转 换的次数;另一方面,规划中根据网络路由情况,对父节点和子节点及兄弟节点的唤醒时间 进行了适应性调整,可以尽可能多的将节点的空闲侦听状态转换为睡眠状态,避免了空闲侦 听的能量损耗。
(2)本发明中,骨干网络的路由结构是算法的输入条件,因此,算法可以针对不同的路 由结构计算出最适合的方案。同时,发明中的规划在网络运行过程中是实时更新的,因此算 法可以适用于静态路由和动态路由。
(3)本发明中设计了基于能耗的跨层优化模型,模型中综合考虑了物理层、MAC层、 网络层的各项因子,可以更好的根据网络实际情况计算出能耗最优的规划方案,避免了单方 面考虑某些因子带来的弊端。
附图说明
图1为本发明中的骨干网络簇头节点运行周期图;
图2为本发明的总体流程图;
具体实施方式
下面将结合附图和实施例对本发明作进一步的详细说明。
本发明是一种多对一分簇无线传感器网络环境下节点睡眠调度方法,设计节能的节点运 行周期图,根据节点运行周期图及物理层、MAC层、网络层参量构建基于能耗的跨层优化模 型,保证每个骨干网络节点在一个周期内只唤醒一次,减少节点处于空闲侦听的时间,降低 网络能耗,通过调节各个节点的数据聚合率,保证能耗均匀分布于骨干网络的各个节点上, 延长网络寿命,方法流程如图2所示,主要包括以下几个步骤:
步骤1:进行网络初始化;
对无线传感器网络环境进行初始化,完成网络中节点的部署、分簇,部署后,得到节点 分布信息,分簇后,每个簇内有一个簇头节点,所有簇头节点构成骨干网络。
设定数据聚合树中SINK(汇聚节点)节点的编号为1,骨干网络节点的编号在节点部署 时随机分配。
步骤2、根据路由查找算法,获取无线传感器网络的数据聚合树,得到路由矩阵R;
选取现有的一种路由查找算法(例如:OSPF,Open Shortest Path First开放式最短 路径优先),将骨干网络节点分布信息作为输入,得到适应于无线传感器网络的数据聚合树, 树的顶点为SINK节点。根据数据聚合树得到路由矩阵R。
根据路由矩阵R,获取父节点矩阵FN、子节点矩阵CN、层矩阵L、兄弟矩阵BN,用 于后续能耗计算中父节点、子节点、层数、兄弟节点的查找。具体为:
路由矩阵R为:
其中
其中:N表示N个骨干网络中簇头节点的数量,rij表示簇头节点i到簇头节点j的链路 通断情况。
路由矩阵R具有下述特点:对角线为0,对称位置为相反数,ri.表示簇头节点i与其他 簇头节点的连通关系,由于是树形结构,所以每个簇头节点只有一个父节点,有多个子节点, 则ri.中只有一个为+1,其余为0或-1,-1的数量为子节点的数量。
父节点矩阵FN:
簇头节点i的父节点编号用fni表示,则父节点矩阵为:FN=[fn1 fn2 … fnN]。
若簇头节点j是簇头节点i的父节点,路由矩阵中rij=1,则fni=j,若簇头节点i没有 父节点则fni为0。
子节点矩阵CN:
簇头节点i的子节点编号用表示,中各个子节点的编号按递增顺序排列,则子节 点矩阵为
根据路由矩阵R,若簇头节点j是簇头节点i的子节点,有rij=-1,则
层矩阵L:
簇头节点i在数据汇聚树中的层数用Li表示,即L=[L1 L2 … LN]。
其中,设定sink节点编号为1,位于第一层,即L1=1。
根据子节点矩阵,可以获得每个簇头节点的子节点,若一个簇头节点的层数为l,则其子 节点的层数为l+1,以此类推,可以计算出所有节点的层数。
兄弟节点矩阵BN:
簇头节点i的兄弟节点编号用表示,中各个兄弟节点的编号按递增顺序排列,即
根据父节点矩阵和子节点矩阵,每个簇头节点可以获得与该节点有着相同父节点的所有 子节点编号,即为该节点的兄弟节点编号。
步骤3、确定簇头节点的周期运行方法,构建基于能耗的跨层优化模型,获取每一个簇 头节点的睡眠调度方法。
(1)确定簇头节点的周期运行方法;
簇头节点运行周期如图1所示,每个簇头节点的运行方法为:
1、簇头节点处于睡眠状态,当簇头节点需要收发数据时,将簇头节点由睡眠状态切换至 工作状态;
簇头节点的状态转换(SC)时间为:父节点比第一个子节点晚唤醒ΔT,保证父节点可 以开始收子节点数据的时候,该子节点已经准备好发送数据;兄弟节点之间,后面的子节点 要依次比前一个子节点晚唤醒Δt,保证在前一个子节点完成发送数据后,该子节点恰好准备 好向父节点发送数据。
2、簇头节点收集簇内数据;
簇头节点收集簇内节点在一个周期内的感知数据。簇内节点是提前部署好的、只用于感 知数据并将数据上传给簇头节点,不具备路由与网关的功能。簇内节点在对应簇头节点开始 工作后,将一个周期内感知的数据上传给簇头节点,由簇头节点经由骨干网络的数据聚合树 将数据汇聚到SINK节点。
3、如果簇头节点有子节点,则簇头节点收集子节点数据;
骨干网络中簇头节点收集数据聚合树中其子节点的数据,子节点也是骨干网络中的簇头 节点,这时骨干网络簇头节点的作用是转发其他簇头节点的数据。
4、簇头节点向父节点发送数据;
骨干网络簇头节点收集数据完毕之后,经过数据聚合,将自己存储的数据上传给父节点, 由父节点担任数据转发的职责。子节点向父节点发送数据之前,要和父节点进行同步,周期 性的向父节点发送同步请求包(SYN),得到父节点确认包(ACK)后,再开始数据发送。 数据发送完毕后,子节点需要等待父节点发送的反馈包(FB),来判断数据是否发送成功, 若本次数据发送失败,存储数据,等待簇头节点下一次唤醒(由睡眠状态切换至工作状态) 时优先重新发送本次数据。
5、簇头节点进入睡眠;
骨干网络簇头节点完成数据的收集与发送工作后,避免不必要的空闲侦听带来的能耗损 耗,将节点切换为睡眠状态,降低节点能耗。
(2)构建基于能耗的跨层优化模型;
1、获取参数:
丢包率矩阵P为:
当rij=0时,pij=0
其中:pij表示簇头节点i到簇头节点j的链路上的丢包率。
数据传输率矩阵F为:
当rij=0时,fij=0
其中:fij表示簇头节点i到簇头节点j的链路上的数据传输率。
能耗矩阵E为:
其中:i表示簇头节点编号,j表示节点的能量属性编号,Ei1表示簇头节点i的状态转换 能耗;Ei2表示簇头节点i的收簇内数据的能耗;Ei3表示簇头节点i的收子节点数据的能耗; Ei4表示簇头节点i的发送数据的能耗;Ei5表示簇头节点i的睡眠能耗;Ei6表示簇头节点i 的数据处理能耗。
第i个节点的能耗为所有节点的总能耗为
睡眠调度矩阵T:
其中:i表示簇头节点编号,j表示节点的时间属性编号,ti1表示簇头节点i的下次唤醒 的时间;ti2表示簇头节点i的下次收簇内数据的时间;ti3表示簇头节点i的下次收子节点数 据的时间;ti4表示簇头节点i的下次发送数据的时间。
数据聚合率矩阵AG:
由于网络为数据聚合树结构,容易发现,越靠近SINK节点的骨干网络节点,需要转发 的数据量越大,能量消耗也就越大,有可能导致靠近SINK节点的骨干节点能耗过早耗尽, 进而整个网络瘫痪的情况。因此,需要在网络中加入数据聚合的策略,根据节点需要传输的 数据量不同,设定不同的数据聚合率,一定程度上降低靠近SINK节点的骨干节点需要传输 的数据量,尽可能使骨干网络中各个节点的能耗均匀。
簇头节点i的数据聚合率为agi,即AG=[ag1 ag2 … agN]。
基本功耗:
状态转换一次能耗为Echange,进行一次数据聚合的能耗为Eagg,发送数据功耗为Psend,接 收数据功耗为Prec,空闲侦听功耗为Pidle,睡眠功耗为Psleep。
反馈矩阵FB:
簇头节点i上一次发送数据的反馈情况用fbi表示,当需要重新发送数据时,fbi记录为 需要重新发送的数据量。初始化时fbi均为0。
FB=[fb1 fb2 fb3 … fbN],其中
由于节点i向父节点发送数据的丢包率为故fbi=Ssend,i的概率为Ssend,i表示 需要重新发送的数据量。当节点i的数据发送成功时,节点i将收到反馈信息ACK,则fbi=0; 当节点i的数据发送失败时,节点i将收到反馈信息NAK或者收不到反馈信息,则fbi=Ssend,i, 其中,Ssend,i表示节点i本次发送的数据量。
设定其他参数:
tbrc_i表示簇头节点i可以开始接收子节点数据的时刻;
tbs_i=ti1+ti2+ti3表示簇头节点i可以开始向父节点发送数据的时刻。
SSYN表示SYN包的大小;
SACK表示ACK包的大小;
SFB表示FB包的大小;
2、推导过程
各部分能耗的计算:
对于簇头节点i,有Ei=Ei1+Ei2+Ei3+Ei4+Ei5+Ei6,表示节点i在一个周期内的能耗, 具体计算如下。
(1)Ei1:状态转换能耗
若按照之前的规划,节点i在一个周期内唤醒一次,故Ei1=Echange。
(2)Ei2:收簇内数据的能耗
骨干节点i就表示网络中第i个簇,设簇内有Ki个节点,每个节点的数据到达率为 λik(bit/s),簇内网络运行周期为Ti_ch,簇内划分为Gi个组,则每组工作时间为Ti_ch/Gi,也 就是簇头节点i的工作周期Ti=Ti_ch/Gi。
则节点i在一个工作周期内需要在簇内采集的数据量为若簇内数据上传 时的数据传输率为μi(bit/s),则节点i收簇内数据的时间为
故:
(3)Ei3:收子节点数据的能耗
设节点i共有Mi个子节点,根据节点运行周期图,可以写出节点i接收第m个子节点的 能耗为:Ei3,m=Ewait_SYN,m+Erec_SYN,m+EACK,m+Ereceive,m+EFB,m。
其中,Ewait_SYN,m为等待同步的能耗,Erec_SYN,m为接收同步包的能耗,EACK,m为发送ACK 的能耗,Ereceive,m为接收数据的能耗,EFB为发送反馈的能耗。具体计算如下:
等待同步的能耗:Ewait_SYN,m=Pidle·twait_SYN,m
其中,
其中,表示节点i的第m个子节点准备好向父节点发送数据的时 刻,分别表示节点i的第m个子节点的第1、2、3个时间属性,tSYN表示 节点发送/接收同步请求包(SYN)的时间,tinter_SYN表示两次发送SYN的时间间隔;
表示节点i准备好接收第m 个子节点数据的时刻,其中,tACK表示节点发送/接收确认包(ACK)的时间,trec,m-1表示节 点i第m-1个子节点接收数据的时间,tFB表示节点发送/接收反馈包(FB)的时间;
表示节点i的第m个子节点进行同步时发送的未收到回复包的同步 包的数量。
接收同步包的能耗:其中,表示簇头节点i的第m个子节点到 簇头节点i的链路上的数据传输率。
发送ACK的能耗:其中,表示簇头节点i到簇头节点i的第m个子 节点的链路上的数据传输率。
接收数据的能耗:
用表示接收的数据包大小,则
发送反馈的能耗:
(4)Ei4:发送数据的能耗
根据节点运行周期图,可以写出:
Ei4=ESYN+Einter_SYN+Erec_ACK+Esend+Erec_FB
其中,ESYN为发送同步请求包(SYN)的能耗,Einter_SYN为同步请求间隔能耗,Erec_ACK为 接收确认包(ACK)的能耗,Esend为发送数据的能耗,Erec_FB为接收反馈包(FB)的能耗。 具体计算如下:
节点i的父节点为fni,i为fni的第c个子节点,节点i准备发送数据的时刻为tbs_i,父 节点准备接收其数据的时刻为则有:
发送同步请求包的能耗:ESYN=Psend·(si+1)tSYN
其中,表示发送同步请求包(SYN)的时间,表示从簇头节点i到父节点 的链路的数据传输率,表示节点i请求同步过程中发送的未得到回复的同 步包的数量。
同步请求间隔能耗:Einter_SYN=Pidle·si·tinter_SYN。
接收ACK的能耗:EACK=Prec·tACK,其中
发送数据的能耗:
这里发送的数据包括两部分,簇内采集的数据和从子节点收集的数据。如果节点上一次 数据发送不成功,则需要优先发送上一次的数据,再发送本次采集的数据。
簇内采集的数据和从子节点收集的数据需要进过数据聚合后再发送,设经数据聚合后, 节点i需要向父节点发送的数据量为
则发送数据的能耗为
接收反馈的能耗:EFB=Prec·tFB,其中
(5)Ei5:睡眠能耗
每个节点在进行下一睡眠调度方法时,暂不删除当前睡眠调度矩阵T,因为T要作为下 一次规划的依据。当前的矩阵为T,下一次的矩阵为T’,完成规划进入睡眠状态之前,令 T=T’,T’清空。
则节点i在下一个周期内睡眠时间为tsleep=ti1′-(ti1+ti2+ti3+ti4)。
节点i在下一个周期内的睡眠能耗为Ei5=Psleep·tsleep。
(6)Ei6:数据处理能耗
数据处理能耗是指节点进行数据聚合过程中的能量损耗,每个节点在一个周期内进行一 次数据聚合,故Ei6=Eagg。
综上,可以计算出网络在一个周期内的总能耗为:
可以得到优化模型为:
minEtotal
0<agi<1(0<i≤N)
约束条件中,表示父节点与其第一个子节点的唤醒时刻的时间差, 表示簇头节点与其第一个兄弟节点的唤醒时刻的时间差,δ<<1, 0<agi<1(0<i≤N)表示簇头节点i的数据聚合率的范围,表示簇头节点i的数 据到达率要小于该节点向父节点发送数据的数据传输率,其中,Mi表示簇头节点i所在簇的 簇内节点数量,表示簇头节点i所在簇的簇内节点平均数据到达率,表示簇头节点i 到父节点的链路的数据传输率。
根据约束条件,求解Etotal最小值,得到睡眠调度矩阵T,通过睡眠调度矩阵T确定每个 簇头节点的下次唤醒的时间、下次收簇内数据的时间、下次收子节点数据的时间、下次发送 数据的时间。
(3)获取每一个簇头节点首次的睡眠调度方法;
通过步骤(2)中得到的基于能耗的跨层优化模型,确定了步骤(1)中簇头节点的周期 运行方法中的时间,得到了每一个节点的首次的睡眠调度方法,每一个簇头节点首次的睡眠 调度方法由SINK节点完成,并且依次告知无线传感器网络中其他簇头节点。
步骤4、无线传感器网络根据节点睡眠调度方法,每一个节点根据该节点的睡眠调度方 法开始运行,向父节点上传数据。
步骤5、当每个节点在向父节点发送数据之后,进入睡眠状态之前,根据当前无线传感 器网络状态,获取基于能耗的跨层优化模型的输入(网络状态的改变主要是当前各个簇头节 点需要发送的数据量的变化和相邻节点睡眠调度方法的变化),采用步骤3中(2)构建的基 于能耗的跨层优化模型,获取该节点下一次的节点睡眠调度方法,并将该方法告知该节点的 父节点和兄弟节点。
步骤6、无线传感器网络判断簇头节点的能量是否耗尽,如果是,转入步骤7,否则, 返回步骤4。
步骤7、如果骨干网络中有簇头节点能量耗尽,采用路由查找算法,判断当前剩余的骨 干网络节点是否能够重新构建数据聚合树(当路由查找算法,有输出的时候,判断为骨干网 络节点可以重新构建数据聚合树),若能够重新构建数据聚合树,则返回步骤2,否则骨干网 络能量耗尽,无线传感器网络终止运行。
机译: 无线传感器网络系统,一种在无线传感器网络系统中设置多个传感器节点的方法,以及一种按传感器节点的面积计算传感能量消耗的方法,能够进行最佳传感器节点设置
机译: 占空比无线传感器网络的占空比无线传感器节点系统和占空比无线传感器网络的传输调度设置方法
机译: 战术移动ad-hoc网络中的调度节点,以及网络环境学习方法,以及调度方法