一种用于智能交通系统的非均匀分簇路由的方法

摘要

本发明公开了一种用于智能交通系统的非均匀分簇路由协议的方法，采用混合蛙跳算法，包括以下步骤：建立网络模型与分簇策略，簇间路由参数初始化，簇间路由局部和全局优化，簇半径的动态调整。本发明可提高感知网络的生存周期、减短网络的收敛时间并且改善网络的负载均衡。

主权项

一种用于智能交通系统的非均匀分簇路由协议的方法，包括以下步骤：（1）建立网络模型与分簇策略：在二维平面区域：，所有传感器节点随机分布，将区域网格化，其格状网每个正方形区域为，边长根据应用任务的求解精度而定；两个节点的位置分别为和，则两个位置之间的距离为：将该区域划分成个区，的数量由该区域的长度和分区节点的通信半径确定，汇聚节点( Sink )节点部署在区域外的一个固定位置；为了实现能耗均衡，距离汇聚节点( Sink )近的分区内的簇数目应多于远的分区；由于交通环境下车辆节点的高移动性，每个簇的簇头由Sink节点指定为该簇区内的一个固定设施；其它节点与簇头之间单跳通信，簇头可通过调整通信半径控制成员数以减小通信负载；对于相邻的两个簇簇头和,则，其中表示与之间的距离，和表示相应的半径；此外，不在任何一个簇通信半径覆盖下的传感器节点可采用链式结构的多跳通信，基于贪婪算法选择信号强度最好的中继节点传送感知数据，以此方式将数据传递至距离最近的簇内的成员节点；该节点作为链首进行一次数据融合后，将数据包发送至簇头；网络中的每一个传感器节点，都有一个唯一的标志（ID），由可信中心（Trusted  Authority）负责对节点认证、注册并授权，节点通过标志（ID）和可信中心（Trusted  Authority）签发的数字证书相互验证身份；若节点发射比特数据到距离为的位置，则发送端的能量为：接收端的能量为：（2）簇间路由参数初始化：簇区内簇头周期性地向其他成员节点发送询问报文以同步时间；每一轮采样,簇头将接收到的感知数据进行融合，生成新的数据包传送至汇聚节点（Sink）；传送时，会选择相邻簇头作为中继节点转发数据包；因此，从源点到汇聚节点（Sink）之间可生成一条或多条不同的路径；除与汇聚节点（Sink）一跳距离的簇外，簇头随机生成只青蛙，每只青蛙个体表示一条从到汇聚节点（Sink）的可行路径，即，其中表示解空间的维数，，即为生成的初始群体；青蛙个体适应度函数为：式(5)中，，表示是路径上的一个节点，表示是簇内成员节点，表示簇头对成员节点接收/发送数据所消耗的能量，表示是的相邻簇头，表示对接收/发送数据所消耗的能量，表示融合数据所消耗的能量，表示进行相应计算所消耗的能量；函数描述路径的总体能量消耗，包括该路径上各节点的计算代价和通信负荷，每一轮数据采样，簇头接收簇内成员节点和来自相邻簇头的消息，计算出各能耗参数并更新从该簇头到汇聚节点（Sink）的每条路径的代价，其中，系数为各种参数在节点总体能耗中的比重；簇间最优路径问题等于青蛙最优解问题；最优解是目标函数取最小值，即取最大值；将生成的青蛙适应度按降序排列成，并划分成个种群，构造子种群，的数值由中源点的下一跳节点的个数来决定；每个子种群包含只青蛙，满足下列关系：    （3）簇间路由优化：簇间路由优化步骤包括簇间路由局部优化步骤以及簇间路由全局优化步骤；（3.1）簇间路由局部优化：簇间路由局部优化是对青蛙种群划分的子种群分别进行局部搜索；簇间路由局部优化步骤1：在第轮,，计算子种群的适应度，以概率一一进行更新，并找出最优解和最差解；簇间路由局部优化步骤2：与进行交叉替换操作，即查找两条径中的相同节点，从选中的一个公共节点开始到下一个公共节点对进行链路替换，如果两条路径仅有一个相同节点，则取汇聚节点（Sink）为下一个公共点；簇间路由局部优化步骤3：计算交叉后最差解的适应度，如果大于替换前最差解适应度，则替换成功，否则，交叉失败，如果交叉失败，则再选用全局最优解对进行交叉替换，如果仍没有得到改进，则随机产生一个新的青蛙来代替原；（3.2）簇间路由全局优化：簇间路由全局优化步骤1：本轮搜索结束后，进行新一轮局部搜索；簇间路由全局优化步骤2：重复簇间路由全局优化步骤1，经过轮局部优化后，将所有子种群的解重新混合在一起，按适应度降序排列，重新划分簇群；簇间路由全局优化步骤3：重复簇间路由全局优化步骤2，直到满足目标函数值最小为止；（4）簇半径的动态调整：每一轮采样,簇头可计算其竞争半径如下：式(6)中，为簇区内成员节点到汇聚节点（Sink）的最大距离和最小距离，为簇头竞争半径的最大取值，为0‑1之间的参数，用来控制取值范围；簇内成员节点与簇头采用单跳通信方式通信，成员节点除了发送自身采集的数据，还需转发来自簇外其它节点的通过链式结构传送的数据；为避免簇头节点承担过重负担，消耗更多的能量，使得簇头过早失效或丢弃数据包，从而造成感知空洞，为此，非均匀分簇路由协议（UCSNP）采取一种动态的簇半径优化策略以调整节点间负载均衡，设置权值计算公式如下：式(7)中，为0‑1之间的参数，为簇内成员节点在本轮采样中所消耗的能量，为簇头在本轮采样中所消耗的能量，为簇头在本轮的通信半径，从式(7)可得出，权值由成员节点总能耗与簇头能耗之比和成员节点到簇头距离总和与到簇头通信半径之比来决定。