基于自动机和生命游戏的无线传感器网络广播认证方法

摘要

无线传感器网络由于其特征使之面临较多的隐患。本发明方法针对无线传感器网络认证中基站的覆盖范围受限、网络流量特殊分布这两方面的问题，提出了基于自动机和生命游戏的无线传感器网络广播认证方法，该方法可扩大基站的覆盖范围实现全网节点的广播，模拟WSN网络流量的分布形态。主要通过改进的确定有穷自动机、分簇算法、生命游戏算法等多种方式相结合，来实现无线传感器网络广播认证。并设计了具体的技术方案和步骤流程，显著区别于现有的WSN网络中使用的广播认证方法。在基站节点的通信范围、网络中节点能量的合理分配、网络流量形态的模拟等方面具有有益效果。

主权项

1.基于自动机和生命游戏的无线传感器网络广播认证方法，其特征在于该认证流程划分为基于有穷自动机DFA的分簇过程，基于生命游戏的无线传感器网络(WSN)数据流量的模拟过程，哈希Hash密钥链的构造、基于网络流量的发布和验证过程三部分：一.基于DFA的分簇过程将DFA作为每个节点的属性特征，即每个节点都含有某一种改进的模n有穷自动机模nDFA，用于识别和处理分簇建立过程中的接收信号，改进的模nDFA通过对接收信号的处理得到各自的完成代价，即当接收信号和模nDFA确定时，所对应的完成代价也确定，这样，综合完成代价、能量值等因素来确定所需要选择的节点的优先级，选择优先级高的节点作为所需要的节点；基站的邻居节点建立过程步骤1）基站节点广播发送“邻居建立”消息，即包含[消息类型，源节点ID，一串随机的0、1字符串]的数据包；步骤2）若接收节点尚未有簇头节点，则立即反馈应答消息，即[消息类型，源节点ID，本节点ID，能量信息，完成代价]，并将基站节点作为簇头节点记录下来；步骤3）基站节点将所有接收节点信息存入邻居节点列表中，并以完成代价升序排列；基站的簇头选举过程步骤4）基站节点从上向下遍历邻居列表，选择响应时间小于时间阈值T_T、能量值大于能量阈值Q_T的节点为簇头节点；簇头数量可通过调整T_T和Q_T来确定；步骤5）基站节点广播发送“簇建立消息”，按照[消息类型，源节点ID，选为簇头节点ID]的格式进行；步骤6）接收节点收到“簇建立消息”后，若被选举为簇头节点，则将类型标识改为“簇头”，簇头节点ID改为自己的ID；簇头的邻居节点建立过程步骤7）任一簇头节点i广播发送“邻居建立”消息，即包含[消息类型，源节点ID，一串随机的0、1字符串]的数据包；步骤8）若接收节点尚未有簇头节点，则立即反馈应答消息，即[消息类型，源节点ID，本节点ID，能量信息，完成代价]，并将节点i作为簇头节点记录下来；步骤9）节点i将所有接收节点信息存入邻居节点列表中，并以完成代价升序排列；簇头的中继节点的选举过程步骤10）簇头节点i从上向下遍历邻居列表，选择类型标识为“普通”、响应时间小于时间阈值T_Ti、能量值大于能量阈值Q_Ti的节点为中继节点；中继节点的数量可通过调整T_Ti和Q_Ti来确定；步骤11）节点i广播发送“中继节点选举消息”，按照[消息类型，源节点ID，选为中继节点ID]的格式进行；步骤12）接收节点收到“中继节点选举消息”后，若被选举为中继节点，则将类型标识改为“中继”；中继的邻居节点建立过程步骤13）任一中继节点j广播发送“邻居建立”消息，即包含[消息类型，源节点ID，一串随机的0、1字符串]的数据包；步骤14）若接收节点尚未有簇头节点，则立即反馈应答消息，即[消息类型，源节点ID，本节点ID，能量信息，完成代价]；步骤15）中继节点将所有接收节点信息存入邻居节点列表中，并以完成代价升序排列；中继的后继簇头节点选举过程步骤16）中继节点j从上向下遍历邻居列表，选择类型标识为“普通”、响应时间小于时间阈值T_Ti、能量值大于能量阈值Q_Ti的节点为簇头节点；中继节点的数量可通过调整T_Ti和Q_Ti来确定；步骤17）节点j广播发送“簇头节点选举”消息，按照[消息类型，源节点ID，选为簇头节点ID]的格式进行；步骤18）接收节点收到“簇头节点选举消息”后，若被选举为簇头节点，则将类型标识改为“簇头”，簇头节点ID改为自己的ID；新节点的加入过程步骤19）任一新节点k广播发送“邻居建立”消息，即包含[消息类型，源节点ID，一串随机的0、1字符串]的数据包；步骤20）接收节点立即反馈应答消息，即[消息类型，源节点ID，本节点ID，能量信息，完成代价，节点类型]；步骤21）节点k将所有接收节点信息存入邻居节点列表中，将“簇头”节点优先排在前面，再以完成代价升序排列；步骤22）节点k从上向下遍历邻居列表，若没有邻居则此节点失效，加入失败，结束；步骤23）若邻居节点中有簇头节点，则向簇头发送“请求加入”消息，按照[消息类型，簇头节点ID，本节点ID]的格式进行；步骤24）簇头节点收到请求消息后，发送“新邻居更新”消息，即包含[消息类型，源节点ID，新节点ID，一串随机的0、1字符串]的数据包；步骤25）节点k立即反馈应答消息，即[消息类型，源节点ID，本节点ID，能量信息，完成代价]，并将簇头ID记录下来；步骤26）簇头节点按照完成代价由小到大的顺序，将节点k的信息插入邻居节点列表中；步骤27）若邻居节点全部为普通节点，节点k从上向下遍历邻居列表，选择响应时间小于时间阈值T_Ti、能量值大于能量阈值Q_Ti的节点p为中继节点，向节点p发送“中继节点选举”消息，按照[消息类型，源节点ID，选为中继节点ID]的格式进行；步骤28）节点p收到被选举消息后，发送“新邻居更新”消息，即包含[消息类型，源节点ID，新节点ID，一串随机的0、1字符串]的数据包；步骤29）节点k立即反馈应答消息，即[消息类型，源节点ID，本节点ID，能量信息，完成代价]，并将中继ID记录下来记为簇头节点；二基于生命游戏的WSN数据流量的模拟过程采用L*L的正方形网格的二维模型，每个网格为一个元胞，“工作”状态的元胞数即为网络流量数；其中，L值由网络的最大流量数dg_max确定，即L*L≥dg_max；将一维的网络流量映射到二维的网格中，通过对网格生命状态的模拟近似得到网络流量的分布；每个离散时刻点所有“工作”状态的网格数即为对应时间段内基站节点需要广播的数据包个数；对应的时间段为(q-1)*t_dg到q*t_dg，其中t_dg为一段固定的时长，q为时刻点，q=1,2,3,…；网络启动时流量的模拟过程：步骤30）置L*L个网格的初始状态为0，即表示“休眠”状态，设初始时刻时间为0，即0*t_dg；步骤31）随机选择rdm个网格，将其状态置为1，即表示“工作”状态，此时刻记为1*t_dg，表示0*t_dg到1*t_dg时段内数据包流量为rdm；rdm为小于2*L的随机值；步骤32）所有的网格会根据生命游戏的S23/B3规则，随着t_dg前的系数q的递增不断地变换其状态，对应于(q-1)*t_dg到q*t_dg时段内数据包流量不断变化；步骤33）网络启动过程中，即从1*t_dg到20*t_dg时间段，流量是一个宏观的递增过程，因此，当“工作”状态网格数目小于rdm/2时，需要增加rdn个“工作”网格，即再次随机选择rdn个网格，将其状态置为1；rdn为小于rdm的随机数；网络稳定时流量的模拟过程：步骤34）网络稳定过程中，即从21*t_dg往后的时间段，所有的网格会根据生命游戏的S23/B3规则，随着t_dg前的系数q的递增不断地变换其状态，对应于(q-1)*t_dg到q*t_dg时段内数据包流量不断变化；步骤35）在网络稳定过程中，若出现数据流量长时间低于阈值num_small=L的情况，则需要增加rdk个“工作”网格，即随机选择rdk个网格，将其状态置为1；其中，长时间表示t_dg递增了30次，即表示整个网格的状态连续变换了30次；rdk为小于L的随机数；三Hash密钥链的构造、基于网络流量的发布和验证过程假设在(q-1)*t_dg到q*t_dg时间段内的数据包总数目为dg_q，且以速度dg_q/t_dg匀速到达基站，即表示在(q-1)*t_dg到q*t_dg时间段内，dg_q个数据包每个以t_dg/dg_q的时间间隔依次到达基站；将一个t_dg长的时间段可分为dg_q个小时段，每个小时段长为t_dg/dg_q，每个小时段用I表示，第i个小时段记为I_i；每一小时段拥有一对对称密钥K_i，用于加密和解密需要广播的内容，并且，在第I_i小时段内广播第i个广播密文和公布第i-d个密钥K_i-d，显然，发布广播密钥较发布密文的时间差d*t_dg/dg_q要长于基站节点与最远节点之间的一次包交换时间；d表示密钥发布的延迟尺寸；步骤36）基站生成一个随机数R，并利用伪随机函数H，计算H(R)，H²(R)，…，Hⁿ(R)分别作为n次会话的密钥存放在密钥池中，将Hⁿ(R)作为密钥头K₀，并规定第i小时段的密钥K_i=H^n-i(R)，其中，i=1,2,…,n，且H⁰(R)=R，n>>dg_q；步骤37）基站广播初始参数消息，即[消息类型，源节点ID，当前基站时钟T_B，开始时间T₁，密钥头K₀，时间间隔t_dg/dg_q，密钥发布的延迟尺寸d，最大时钟差异δ_max]；步骤38）每级簇头节点和中继节点转发基站的广播初始参数消息；步骤39）各节点收到后，将各自的时钟与基站节点的时钟同步，并且记录下T₁、K₀、t_dg/dg_q、d、δ_max等信息；步骤40）基站节点在第i个小时段内，广播第i个数据包密文和发布第i-d个密钥K_i-d；步骤41）接收节点收到第i个t_dg/dg_q的数据包密文后，判断密钥K_i是否已经发布过，若已经发布则丢弃此包；若尚未发布则先验证K_i-d的真假，若为真则缓存此包并且解密第i-d时段密文数据包，否则丢弃；步骤42）(q-1)*t_dg到q*t_dg时间段内的数据包广播完成后，hash密钥链从用到则从q*t_d往后的时间段的数据包使用从开始往后的密钥，以此类推直到密钥链用完。