[发明专利]节点数未知单跳网络中基于同步时间片的邻居发现方法

摘要

一种节点数未知单跳网络中基于同步时间片的邻居发现方法，所述网络中每个节点包括报文发送模块、报文接收模块和邻居发现主模块，其中所述报文发送模块用于不同报文的组装，报文分为DISCOVERY报文和SUCCESS报文；所述报文接收模块用于接收报文；所述邻居发现主模块分为时间片管理模块、邻居信息模块、节点信息模块。在网络节点间时间片同步时，对于网络节点总数n未知的情形,将运行时间分为多个阶段,第r个阶段持续2r+1e个时间片，每个时间片又分为两个子时间片，设置节点报文发送模块发送概率是1/(2r‑b)。经过本发明方案的处理，可以使得上述邻居发现方法的运行复杂度为Θ(n)。 1

主权项

1.一种节点数未知单跳网络中基于同步时间片的邻居发现方法，所述网络中节点总数n未知，节点间时间片为同步，其中每个节点包括报文发送模块、报文接收模块和邻居发现主模块，其中所述报文发送模块用于不同报文的组装，报文分为DISCOVERY报文和SUCCESS报文；所述报文接收模块用于接收报文；所述邻居发现主模块分为时间片管理模块、邻居信息模块、节点信息模块；其中所述时间片管理模块用于把邻居发现过程的分为若干个时间片，在某个具体的时间片，由邻居发现主模块协调报文发送模块和报文接收模块处理报文；邻居信息模块维护邻居节点列表和已发现邻居节点个数，邻居节点列表包括已发现邻居节点MAC地址一个字段；节点信息模块维护自身信息，包括是否已被邻居节点发现的标志flag和节点自身地址，所述方法包括：

步骤201：在邻居信息模块中初始化已发现邻居节点个数b＝0，初始化邻居节点列表NbrList，在节点信息模块中设置标志flag＝0，执行步骤202；

步骤202：当前节点的时间片管理模块把运行时间分为多个阶段，其中第r个阶段持续2^r+1e个时间片，设置r的初值为1，执行步骤203；

步骤203：判断当前节点是否已经被邻居节点发现同时已经发现所有邻居节点，如果是则结束邻居发现过程，否则跳转到步骤204；

步骤204：判断第r个阶段是否结束，如果结束，跳转到步骤212，否则跳转到步骤205；

步骤205：设置当前节点报文发送模块发送概率是1/(2^r‑b)，执行步骤206；

步骤206：判断当前节点的标志flag是否等于零，等于零表示当前节点未被邻居节点发现，不等于零表示该节点已被邻居节点发现，如果当前节点未被邻居节点发现则跳转到步骤207，否则跳转到步骤208；

步骤207：当前节点时间片管理模块把当前阶段的当前时间片分为两个子时间片，并且控制报文发送模块在第一个子时间片内以概率1/(2^r‑b)发送DISCOVERY报文用来进行邻居发现，如果成功发送DISCOVERY报文则跳转步骤210，否则跳转步骤208；

步骤210：判断当前节点报文接收模块在当前阶段当前时间片的第二个子时间片内信道是否空闲，如果不是空闲的，则跳转到步骤211，否则跳转到步骤204；

步骤211：当前节点已被邻居发现，不再发送DISCOVERY报文，设置节点信息模块中的标志flag＝1，跳转到步骤204；

步骤208：判断当前节点是否成功收到其它邻居节点在当前阶段当前时间片的第一个子时间片内发送的DISCOVERY报文，如果成功接收了DISCOVERY报文，则跳转到步骤209，否则跳转到步骤204；

步骤209：在当前阶段当前时间片的第二个子时间片内当前节点通过报文发送模块发送反馈报文SUCCESS，同时将已接收到DISCOVERY报文的源节点MAC地址加入到邻居节点列表NbrList中，设置已发现邻居节点个数b＝b+1，并返回到步骤204；

步骤212：设置阶段r＝r+1，跳转步骤203。

2.如权利要求1所述的方法，其特征在于，步骤203中判断当前节点是否已经成功发现所有邻居节点的方法是：在一个给定的时间段内，当前节点的报文发现模块没有收到任何DISCOVERY报文，则说明当前节点已经成功发现所有邻居节点，所述给定的时间段定义为：如果节点的报文发送时间为t，则给定的时间段可以是at(a＝2,3,...,n)。

3.如权利要求1所述的方法，其特征在于，步骤207中所述DISCOVERY报文发送成功表明当前阶段当前时间片的第一个子时间片内只有当前节点发送DISCOVERY报文，其它邻居节点接收DISCOVERY报文，当前节点进入等待邻居节点发送反馈SUCCESS报文的步骤(步骤210)；所述DISCOVERY报文发送不成功表明，由于概率的作用当前节点没有发送DISCOVERY报文，此时当前节点进入接收邻居节点DISCOVERY报文的步骤(步骤210)；或者当前节点与邻居节点同时发送DISCOVERY报文，造成冲突发生，此时当前节点和邻居节点同时进入接收DISCOVERY报文的步骤(步骤208)。