1.一种无线网络的路由通信实现方法,其特征在于,所述无线网络的节点为具有路由转发功能的节点,每个节点具有唯一性的节点ID且在一跳范围内定期广播信标帧;
每个节点保存N个n跳节点表以及一个路由表,n=1,2……N,N为正整数且N小于无线网络的直径;n跳节点表和路由表各自包括一个表项,n跳节点表和路由表的表项都由四个域构成:目的节点ID域,下一跳域,路径长度以及生存时间;生存时间随着机器时钟自动衰减,当生存时间衰减为0时,相应的表项被删除;生存时间的最大值由节点平均移动速度以及传输半径决定,设置为2r/v,其中r为节点传输半径,v为节点平均移动速度;
所有节点定期在其自身的1跳范围内广播信标帧,信标帧的负载为N-1个i跳节点表,i=1,2……N-1;节点通过扩展IEEE802.15.4协议中的命令帧实现路由表的建立,命令帧负载第一个字节标识命令帧的负载内容:第一个字节值 负载内容
15 源节点ID和目的节点ID,路径长度变量
无线网络启动后,开始进行无线网络初始化操作,即节点开始广播信标帧建立n跳节点表;
节点H通过下述过程建立1跳节点表:
步骤101:开始;
步骤102:节点H收到邻居节点的信标帧后,判断自己的1跳节点表中是否存在一个表项,该表项的下一跳域为信标帧的源节点ID,如果是,进行步骤104,否则进行步骤103;
步骤103:节点H在1跳节点表中加入一个新表项,表项的目的节点ID域和下一跳域为信标帧的源节点ID,路径长度为1,生存时间为最大值;
步骤104:执行步骤102到步骤103,直到节点H将所有邻居节点加入到自己的1跳节点表为止;
步骤105:结束;
节点H建立1跳节点表后,通过下述过程建立j跳节点表,j=2……N:步骤701:开始;
步骤702:节点H收到邻居节点的信标帧后,判断信标帧负载中的j-1跳节点表是否为空,如果是,进行步骤705,否则进行步骤703;
步骤703:节点H比较自己的j跳节点表和信标帧中的j-1跳节点表,判断信标帧中的j-1跳节点表中是否存在满足下述条件的表项,如果是,进行步骤704,否则进行步骤705;
条件:该表项的目的节点ID域的值与节点H的j跳节点表中所有表项的目的节点ID域的值都不相同;
步骤704:在节点H的j跳节点表中增加一个表项,表项的目的节点ID域为步骤703中满足条件的表项的目的节点ID域的值,下一跳域为信标帧的源节点ID,路径长度为j,生存时间为最大值;
步骤705:节点H比较j跳节点表和m跳节点表,m=1…j-1,判断j跳节点表中是否存在满足下述条件的表项,如果是,进行步骤706,否则进行步骤707;
条件:m跳节点表中存在一个表项,该表项的目的节点ID域的值等于j跳节点表中该表项的目的节点ID;
步骤706:节点H从j跳节点表中删除满足上述条件的表项;
步骤707:重复步骤702至步骤706,直到节点H将距离自己j跳的节点都加入到j跳节点表为止;
步骤708:结束。
2.根据权利要求1所述的无线网络的路由通信实现方法,其特征在于,无线网络初始化结束后,如果节点X启动并加入无线网络后,通过下述过程建立1跳节点表:步骤201:开始;
步骤202:节点X收到邻居节点的信标帧后,在1跳节点表中加入一个新表项,新表项的目的节点ID域和下一跳域为信标帧的源节点ID,路径长度为1;
步骤203:重复步骤202,直到节点X将所有邻居节点加入到节点X的1跳节点表中;
步骤204:结束;
节点X建立1跳节点表后,根据下述过程建立j跳节点表,j=2…N:步骤801:开始;
步骤802:节点X收到邻居节点的信标帧后,比较自己的j跳节点表和信标帧中的j-1跳节点表,判断信标帧中的j-1跳节点表中是否存在满足下述条件的表项,如果是,进行步骤
803,否则进行步骤804;
条件:该表项的目的节点ID域的值与节点X的j跳节点表中所有表项的目的节点ID域的值都不相同;
步骤803:节点X在j跳节点表中增加一个新表项,该表项的目的节点ID域为步骤802中满足条件的表项的目的节点ID域的值,下一跳域为信标帧的源节点ID,路径长度为j,生存时间为最大值;
步骤804:节点X比较自己的j跳节点表和m跳节点表,m=1…j-1,判断j跳节点表中是否存在满足下述条件的表项,如果是,进行步骤805,否则进行步骤806;
条件:该表项的目的节点ID域的值等于m跳节点表中一个表项的目的节点ID域的值;
步骤805:节点X从j跳节点表中删除满足上述条件的表项;
步骤806:重复步骤802至步骤805,直到节点X将所有距离自己j跳的节点都加入到j跳节点表;
步骤807:结束;
节点X建立n跳节点表之后,开始广播信标帧,节点X的邻居节点Y收到信标帧后,进行如下操作:步骤301:开始;
步骤302:节点Y收到节点X的信标帧后,在1跳节点表中加入1个新表项,新表项的目的节点ID域的值和下一跳域的值均为节点X的节点ID,路径长度为1,生存时间为最大值;
步骤303:节点Y比较自己的j跳节点表和信标帧中的j-1跳节点表,判断信标帧中的j-1跳节点表中是否存在满足下述条件的表项,如果是,进行步骤304,否则进行步骤305;
条件:该表项的目的节点ID域的值与j跳节点表中所有表项的目的节点ID域的值都不相同;
步骤304:节点Y在j跳节点表中增加一个新表项,新表项的目的节点ID域为步骤303中满足条件的表项的目的节点ID域的值,下一跳域的值为节点X的源节点ID,路径长度为j,生存时间为最大值;
步骤305:节点Y比较自己的j跳节点表和m跳节点表,m=1…j-1,判断j跳节点表中是否存在满足下述条件的表项,如果是,进行步骤306,否则进行步骤307;
条件:该表项的目的节点ID域的值等于m跳节点表中一个表项的目的节点ID域的值;
步骤306:节点Y从j跳节点表中删除满足上述条件的表项;
步骤307;节点Y广播信标帧;
步骤308:结束;
节点Z收到邻居节点的信标帧后,进行如下操作;
步骤401:开始;
步骤402:节点Z收到邻居节点的信标帧后,判断信标帧的源节点ID是否与节点Z的1跳节点表中的一个表项的目的节点ID域的值相同,如果是,进行步骤404,否则进行步骤403;
步骤403:节点Z在1跳节点表中加入一个新表项,新表项的目的节点ID域的值和下一跳域的值为信标帧的源节点ID,路径长度为1,生存时间为最大值;
步骤404:节点Z比较自己的j跳节点表和信标帧中的j-1跳节点表,判断信标帧中的j-1跳节点表中是否存在满足下述条件的表项,如果是,进行步骤405,否则进行步骤406;
条件:该表项的目的节点ID域的值与j跳节点表中所有表项的目的节点ID域的值都不同;
步骤405:节点Z在j跳节点表中增加一个表项,表项的目的节点ID域为满足步骤404条件的表项的目的节点ID域的值,下一跳域的值为信标帧的源节点ID,路径长度为j,生存时间为最大值;
步骤406:节点Z比较自己的j跳节点表和m跳节点表,m=1…j-1,判断j跳节点表中是否存在满足下述条件的表项,如果是,进行步骤407,否则进行步骤408;
条件:该表项的目的节点ID域的值等于m跳节点表中一个表项的目的节点ID域的值;
步骤407:节点Z从j跳节点表中删除满足上述条件的表项;
步骤408:节点Z判断自己是否执行了步骤403和步骤405,如果是,进行步骤409,否则进行步骤410;
步骤409:节点Z广播信标帧;
步骤410:结束。
3.根据权利要求2所述的无线网络的路由通信实现方法,其特征在于,无线网络初始化结束后,如果节点X移动且离开原来邻居节点之后即无法收到原来邻居节点的信标帧,则删除n跳节点表中的所有表项,然后执行步骤201至204以及步骤801至步骤807重新建立n跳节点表;
节点X建立n跳节点表之后,开始广播信标帧,节点X的邻居节点Y收到信标帧后,进行步骤301至步骤308更新n跳节点表;
无线网络中的节点收到邻居节点的信标帧后,执行步骤401至步骤410更新n跳节点表。
4.根据权利要求3所述的无线网络的路由通信实现方法,其特征在于,节点S与节点E进行通信时,如果节点S的n跳节点表和路由表中所有表项的目的节点ID域的值都不等于节点E的节点ID,那么节点S发起下述过程在路由表中建立到达节点E的路由表项:步骤501:开始;
步骤502:节点S广播类型为15的命令帧,命令帧负载中源节点ID为节点S的节点ID,目的节点ID为节点E的节点ID,路径长度变量为0;
步骤503:无线网络中收到类型为15且帧负载为节点S和目的节点E的命令帧的节点,查看自己的n跳节点表或者路由表,判断是否有目的节点ID域值为节点S的表项,如果是,进行步骤505,否则进行步骤504;
步骤504:步骤503中的节点在路由表中建立一个新表项,新表项的目的节点ID域的值为节点S的节点ID,下一跳域的值为转发该命令帧的节点的节点ID,路径长度为命令帧中的路径长度值加1,生存时间为最大生存时间,进行步骤507;
步骤505:步骤504中的节点判断目的节点ID域的值为节点S的表项的路径长度是否大于命令帧中的路径长度d1加1,如果是,进行步骤506,否则进行步骤507;
步骤506:如果节点S在步骤505中的节点的路由表中,步骤505中的节点则将节点S的路由表表项的路径长度设置为d1+1,下一跳域的值设置为转发该命令帧的节点的节点ID,生存时间设置为最大生存时间,执行步骤507;如果节点S在步骤505中的节点的n跳节点表中,步骤505中的节点则从自己的n跳节点表中删除节点S的表项,然后在d1+1跳节点表中增加一个表项,表项的目的节点ID域的值为节点S的节点ID,下一跳域的值为转发该命令帧的节点的节点ID,路径长度为d1+1,生存时间为最大值,执行步骤507;
步骤507:步骤504或者步骤505或者步骤506中的节点判断节点E是否在自己的n跳节点表或者路由表中,如果是,则进行步骤509,否则进行步骤508;
步骤508:步骤507中的节点广播类型为15的命令帧,命令帧负载中源节点ID为节点S的节点ID,目的节点ID为节点E的节点ID,路由长度为步骤507中的节点的n跳节点表或者路由表中对应节点S的表项中的路径长度,返回步骤503;
步骤509:步骤507中的节点构造一个类型为15的命令帧,命令帧帧头中的目的链路地址为n跳节点表或者路由表中对应节点S的表项的下一跳域的节点ID,命令帧负载中的源节点ID为节点E的节点ID,命令帧负载中的目的节点ID为节点S的节点ID,路由长度为n跳节点表或者路由表中目的节点ID域为节点E的表项中的路径长度值,步骤507中的节点发送该命令帧;
步骤510:无线网络中收到类型为15且目的节点为节点S且源节点为节点E的命令帧的节点查看自己的n跳节点表或者路由表,判断是否有目的节点ID域为节点E的表项,如果是,进行步骤512,否则进行步骤511;
步骤511:步骤510中的节点在路由表中建立一个新表项,新表项目的节点ID域的值为节点E的节点ID,下一跳域的值为转发该命令帧的节点的节点ID,路径长度为命令帧中的路径长度值加1,生存时间为最大生存时间,进行步骤514;
步骤512:步骤510中的节点判断n跳节点表或者路由表中节点E的表项的路径长度是否大于命令帧中的路径长度d2加1,如果是,进行步骤513,否则进行步骤514;
步骤513:如果节点E在步骤512中的节点的路由表中,步骤512中的节点将节点E的路由表项的路径长度设置为d2+1,下一跳域设置为转发该命令帧的节点的节点ID,生存时间设置为最大生存时间,执行步骤514;否则如果节点E在步骤512中的节点的n跳节点表中,步骤
512中的节点则从n跳节点表中删除节点E的表项,并在d2+1跳节点表中加入一个新表项,新表项目的节点ID域的值为节点E的节点ID,下一跳域的值为转发该命令帧的节点的节点ID,路径长度为d2+1,生存时间为最大值,执行步骤514;
步骤514:判断步骤511或者步骤512或者步骤513中的节点是否为节点S,如果是,进行步骤516,否则进行步骤515;
步骤515:步骤514中的节点构造一个类型为15的命令帧,命令帧帧头中的目的链路地址为n跳节点表或者路由表中对应节点S的表项的下一跳域的节点ID,命令帧负载的源节点ID为节点E的节点ID,命令帧负载的目的节点ID为节点S的节点ID,路由长度为n跳节点表或者路由表中目的节点ID域为节点E的表项中的路径长度值,步骤514中的节点发送该命令帧,进行步骤510;
步骤516:结束。
5.根据权利要求4所述的无线网络的路由通信实现方法,其特征在于,节点Y收到邻居节点X的信标帧后,如果节点Y的1跳节点表中存在一个表项,该表项的目的节点ID域的值为节点X的节点ID,节点Y则将该表项的生存时间设置为最大;
节点Y收到邻居节点X的信标帧后,比较自己j跳节点表和信标帧中的j-1跳节点表,如果信标帧中的j-1跳节点表中的目的节点ID等于节点Y的j跳节点表中一个表项的目的节点ID,那么节点Y将j跳节点表中相应表项的生存时间设置为最大值,下一跳域设置为该信标帧的源节点ID;
如果节点S检测到1跳节点表中目的节点X的表项中的生存时间衰减为0,则进行如下操作:步骤601:开始;
步骤602:节点S从1跳节点表中删除目的节点X的表项;
步骤603:节点S查看j跳节点表中是否存在有下一跳域的值为节点X的表项,如果有则进行步骤604,否则进行步骤605;
步骤604;节点S从j跳节点表中删除下一跳域的值为节点X的表项;
步骤605:节点S查看路由表中是否存在有下一跳域的值为节点X的表项,如果有则进行步骤606,否则进行步骤608;
步骤606:节点S广播类型为15的命令帧,命令帧负载中源节点ID为节点S的节点ID,目的节点ID为路由表中下一跳域的值为节点X的表项中的目的节点E的节点ID,路径长度为0,然后从路由表中删除下一跳域的值为节点X的表项;
步骤607:节点S执行步骤503至步骤515建立到达节点E的路由表项;
步骤608:结束。
6.根据权利要求4所述的无线网络的路由通信实现方法,其特征在于,节点S和节点E进行通信的过程包括如下步骤:步骤901;开始;
步骤902:节点S查看所有n跳节点表判断是否有节点E的表项,如果是,进行步骤903,否则进行步骤904;
步骤903:节点S将目的地址为节点E的数据帧转发给节点E对应的n跳节点表表项中下一跳域所对应的下一跳节点,执行步骤907;
步骤904:节点S查看所有路由表判断是否有节点E的表项,如果是,进行步骤905,否则进行步骤906;
步骤905:节点S将目的地址为节点E的数据帧转发给节点E对应路由表项中下一跳域所对应的下一跳节点,执行步骤907;
步骤906:节点S执行步骤501到步骤515建立到达节点E的路由表项,并将目的地址为节点E的数据帧转发给节点E对应路由表项的下一跳域对应的下一跳节点;
步骤907:下一跳节点收到目的地址为节点E的数据帧后,判断自己是否为节点E,如果是进行步骤913,否则进行步骤908:步骤908:步骤907中的下一跳节点查看n跳节点表判断是否有节点E的表项,如果是,进行步骤909,否则进行步骤910;
步骤909:步骤907中的下一跳节点将目的地址为节点E的数据帧转发给节点E对应表项的下一跳域对应的下一跳节点,执行步骤907;
步骤910:步骤907中的下一跳节点查看所有路由表判断是否有节点E的表项,如果是,进行步骤911,否则进行步骤912;
步骤911:步骤910中的下一跳节点将目的地址为节点E的数据帧转发给节点E对应路由表项的下一跳域对应的下一跳节点,执行步骤907;
步骤912:步骤910中的下一跳节点执行步骤501到步骤515建立到达节点E的路由表项,并将目的地址为节点E的数据帧转发给节点E对应路由表项的下一跳域对应的下一跳节点,执行步骤907;
步骤913:结束。