王栽毅, 杨 照
(1. 中国海洋大学信息科学与工程学院, 山东 青岛 266100;2.青岛海洋科学与技术试点国家实验室, 山东 青岛 266237)
近年来,许多研究者应用分簇算法来提高数据传输的性能。分簇算法在无线传感器中有比较深入的研究,文献[1-2]致力研究延长网络的生命周期,这与船联网分簇的目标一致[3],但在船联网中船舶并没有能量限制,在分簇中无需考虑能量问题;其次,在船联网中船舶处于快速移动的状态,网络拓扑结构在不断的变化,而传统的分簇算法并不能根据网络拓扑结构变化来自适应调整分簇;最后,传统的分簇算法主要从能量和路由两方面来考虑其发射功率,进而决定簇的大小,分簇算法往往和路由协议相结合,而在船联网中,簇的大小是由每个时间帧中所划分的时隙数决定的,其中时间帧的长短受消息时延要求的制约,时隙即为网络中的传输时间被划分为一个个时间间隔,每个时间间隔作为一个时隙,每个时隙作为信道资源提供给网络中的节点用于传输信息。因此针对传统的分簇算法在船联网中的缺陷,本文利用改进的模糊C均值(FCM)[4-6]算法进行分簇,解决船舶的拓扑结构不断变化的问题。
目前的数据链路中,船舶编队通信组网方式大多以时分多址(TDMA)[7-13]作为接入算法,TDMA拥有简捷、高效的优点,与此同时也拥有系统固定,传输开销大等劣势。TDMA被广泛用作有效的通信手段。由于TDMA组网的拓扑变化适合船联网中船舶的拓扑变化快速的特点,因此,TDMA广泛作为船联网的组网方式。但当两个彼此远离的簇,在分配时隙时,有两个船舶占用了相同的时隙,当随着速度差的原因,两船进入彼此的通信范围,占用相同时隙的船舶在进行消息传输时就会发生碰撞,在簇头没有重新分配的情况下,会一直碰撞,直到两个簇驶离彼此的通信范围,碰撞才会消失。因此,在进行时隙分配时,合理的分配时隙,能有效的降低消息碰撞率,提高信道的利用率。根据以上时隙碰撞情况,本文提出了利用船舶的速度及位置进行时隙分配的策略。同时,本文提出基于粒子群(Particle Swarm Optimization, PSO)算法的数据传输路径优化算法,以实现海洋观测数据的快速回传。
为改进传统的分簇算法在船联网中的缺陷,本文通过改进的FCM算法,将时隙数量的制约引入到船联网中。首先把规定范围内拥有最多邻居节点的点作为第一个聚类中心点。再根据到前一个聚类中心的距离和自身邻居节点的数量,使用归一化加权方法把距离前一个聚类中心最远和邻居节点数量最多的点作为下一个聚类中心。以此方法得到K个聚类中心vj(j=1,2,…,K),其中K是根据海域的范围和船舶的数量进行确定的。设定迭代的收敛条件φ。
利用公式(1)计算各点到各聚类中心距离的隶属度uij。
(1)
式中:uij表示第i个船舶对第j个簇的隶属度;xi为各船舶的坐标。如果选出的点误差大于φ,使用公式(2)重新计算新的中心点。
(2)
式中m表示模糊加权指数,通常情况下其值为2。
迭代计算,当选取的聚类中心误差小于φ时,停止迭代,获得各节点关于每个聚类中心的隶属度和聚类中心坐标。
因为船联网中的船舶处于变化快速的状态,网络拓扑结构也在不断的变化,因此对簇需要进行维护,在进行维护的同时又需要重新选择每个簇的簇头,这就需要选择发生变化少的节点当作簇头,从而减少维护过程中带来的开销。本文的簇头的选举综合考虑船舶的速度、加速度以及位置这些因素,通过模糊逻辑系统选取最优簇头,实现各船舶的自适应分簇,仿真验证了该方法的有效性与可行性(具体参数及隶属函数见图1和2)。
船舶节点的位置和速度是选取簇头的重要因素,本文使用FIS(Fuzzy logic system)[14]选取簇头考虑三方面输入参数:船舶的速度、船舶到簇中心的距离和船舶自身的加速度。其中表示船舶到簇中心的距离的语言变量分为三个层次:Near、Adequate、Far,表示船舶速度和加速度语言变量Fast、Adequate、Slow。船舶使用分簇算法选取簇头的可能被列为7种情况:Rather Small、Very Small、Small、Middle、Large、Very Large和Rather Large。
模糊规则的设计原则为:如果速度适中、加速度适中、距离簇中心点近,则该船舶成为簇头的机会非常大。本文根据以上情况和基本经验制定了3×3×3=27条模糊规则,使用三角隶属函数表示模糊集的Adequate,使用梯度隶属函数表示Near、Far、Fast的Slow。其中,船舶到簇中心的距离用0~50 km,依据其大小表示距离到簇中心的远近,Near用梯度隶属函数来表示,范围为[-18,-5,5,18],Adequate用三角隶属函数表示,范围为[5,25,45],far用梯度函数表示,范围为[30,45,55,70];船舶自身的加速度的绝对值用0~5 kn/min表示,low用梯度隶属函数表示,范围为[-1.5,-0.7,0.7,1.5],Med用三角函数表示,范围为[0.5,2.5,4.5],High用梯度隶属函数表示,范围为[3,4.3,5.7,7];每个船舶的速度用0~30 kn表示,low用梯度隶属函数表示,范围为[-10,-3,3,10],Med用三角函数表示,范围为[3,18,25],High用梯度隶属函数表示,范围为[18,25,35,42]。各参数的隶属函数如图1和2所示。
首先根据船舶的数量以及海域的范围,确定大约将船舶分为几簇;然后利用改进的FCM算法对整个海域内的船舶进行分簇,利用上文提出的簇头选举算法为每个簇选举最优的簇头,其他不是簇头的船舶根据通信范围的远近,选定所属的簇;最后考虑簇的加入与离开、簇的融合与分离,决定是否重新分簇。
图1 船舶到簇中心距离及隶属函数
图2 船舶速度及模糊规则隶属函数
1.2.1 簇成员的驶入与驶离 船联网中实施分簇算法,经常发生的变化就是船舶的驶入与驶离引起的拓扑变化。当孤立的船舶即没有邻居节点的船舶,进入一个簇头(CH1)的通信范围时,此孤立船舶就会收到CH1的信息,此孤立船舶便会向CH1发送请求加入的信息,CH1收到请求信息后,根据MAC层时隙的数量判断其是否可以加入,若受延时的要求不能加入此簇时,就发送拒绝加入的信息,否则进入等待期。等待期时长为Tw,等待Tw时长以后,如果依然在CH1的通信范围内,该孤立节点就成功加入此簇,成为其中的一员,流程图如图3所示。
图3 簇成员加入流程图
如果其中的一个成员离开CH1的通信范围后,又不在其他簇内,则变为孤立船舶,在Tw内,又回到CH1的通信范围内,因此又成为CH1的成员。若经过Tw后,又离开了CH1的通信范围,此船舶就真正离开了此簇,变为孤立船舶,流程图如图4所示。
图4 簇成员离开流程图
1.2.2 簇成员的再次分配 簇成员的再次分配主要包含两种情况:一种是经过航道分叉口时,一些船舶继续按照原先的航道,另一些船舶进入其他的航道,这样该簇就变为两个簇;另一种可能是伴随着船舶数量的增加,受MAC层时延的要求, 该簇不能容纳此时簇内所有的船舶,就要分出新的簇。航道分叉比较容易,即以前的簇头依然不变,在分出的簇中依然担任簇头;而另外一种是依据簇成员的加入方法加入其它簇中,如果一些船舶都没在其他簇的通信范围内,则这些船舶形成新的簇,在使用分簇算法选出新的簇头。在分簇算法中,MAC层的延时受时隙数量的制,根据MAC层时隙的数量决定簇成员的最大数量wmax时,如果簇内成员达到wmax,若继续有新的节点加入,此时的簇不能容纳所有的簇成员,该簇的簇头便依据船密度β重新规定船舶的通信范围R,使新的船舶通信范围R′满足
2βR (3) 首先,簇头需通过原来的通信范围R播送簇在分配的消息和新规定的通信范围R′,然后,原先想要加入该簇的成员收到消息后将其通信范围改为R′,最后,根据新的通信范围R′,利用分簇算法以及簇头选举算法,形成新的簇。 1.2.3 簇成员的融合 如果两个簇的簇头可以互相进行通信且簇内的数量较少,就需要进行簇成员的融合。进行簇融合的原理为成员少的簇加入成员多的簇内,在满足MAC时延要求和所有成员都在簇头的通信范围内时,就融合为一个,否则将没有融入的其他成员形成另外一个簇。比如在簇A中,拥有1、2、3三个簇成员,而在簇B中包括1、2、3、4四个簇成员。因为A的成员少于B,所以在B通信范围内且满足MAC时延要求下,A成员全部加入B中,如果B不能容纳所有A中的船舶,则B通知A将剩余的船舶形成新的簇,并选取新的簇头,成为新簇,簇融合过程如图5所示。 图5 簇成员融合流程图 根据以上时隙碰撞情况,本文提出了利用船舶的速度及位置进行时隙分配的策略,具体流程为: 在其中一个簇头为CHM,簇成员数量为n的簇M中进行时隙分配时,首先利用簇头选举算法选举出本簇中的簇头,然后给定一个速度值,区分本簇中船舶的快慢,根据给定的速度值,将本簇中的船舶分为两种情况,一种是快速船舶,快速船舶在1、3、5…这样的奇数号时隙中根据位置的前后占用时隙,也就是位置靠前的船舶占用的奇数序号越小。同理,慢速船舶也根据位置和速度在偶数号中占用时隙。比如在快速船舶中,在本簇最前边的节点预约1号,后边相应的预约3、5、7等。当某一种情况下船舶数大于该情况下的时隙数时,可以占用对方的时隙。改进后的时隙分配如图6所示。 图6 基于位置和速度的TDMA时隙分配 簇内成员将数据传输给簇头,簇头进行数据融合,然后簇头之间使用PSO[15]路径优化,用最短的路径将数据传输给基站。 PSO算法是人工智能领域的一种基于群体的优化算法,群体中的每一个个体都当作是问题的一个解,每个个体都有自己的速度,然后按照自己的速度飞行并搜索飞行过程中的最好位置,整个群体同样寻找整个群体的最好位置,经过群体和自己的最好位置不断调整自己的方向和速度,经过不断的变化,找到最后最好的位置。每个个体的更新X和V公式为: (4) 式中:Vid(j)表示个体i在第j轮中的速度;Xid(j)表示个体i在第j轮中的位置;pbest表示粒子当前的最佳位置;gbest表示粒子群当前的最佳位置;w代表惯性权重;c1、c2为学习因子;r1、r2表示0~1之间的随机数。 惯性权重w表示为: (5) 式中:wmax表示惯性权重w的最大值;wmin表示惯性权重w的最小值;t代表当前的迭代次数;T为最大迭代次数。 在本文中,首先利用分簇算法选取簇头,它们组成船舶通信网络数据传输的候选节点集合,然后根据节点通信能力选择船舶通信网络数据传输下一跳节点,最后利用PSO算法优化选中的下一个通信节点,得到其数据传输的最优路径。 通过PSO算法得到船舶进行数据传输最优路径的流程为: (1) 初始化PSO各个参数,即wmax、wmin、c1、c2、T以及n; (2) 利用簇头选举算法得到最优簇头的位置; (3) 初始化所有船舶的位置X和速度V,其中每个船舶代表一个个体; (4) 初始化每个个体的pbest和群体的gbest; (5) 计算每个个体的适应度值,并判断是不是符合约束前提,如果不符合就重新搜索; (6) 更新每个个体的pbest和群体的gbest; (7) 依据公式(5)更新惯w,并利用(4)更新每个个体的X和V; (8) 根据t判断是不是到达了T,如果是,则得到群体的gbest,否则继转到(4),继续寻找gbest; (9) 根据输出的每个个体的gbest求数据传输的最优路径。 本文应用MATLAB软件进行仿真实验。每个船舶可以和通信范围内的所有船舶进行通信。在仿真期间,船只数目保持不变。使用PSO对簇头、簇内节点到基站的数据传输进行优化,仿真参数如表1所示。 表1 船舶数据传输仿真参数 仿真环境下的方形海域内,由一个基站,位置为(0,60 km)和100艘船组成,仿真大范围为120 km×120 km。假设每艘船的通信范围为30 km。应用本文所提船基数据传输与通信节点分簇算法,对实验场景下的船舶目标进行分簇处理,仿真结果如图7所示。容易看出,算法将整个海域范围分为4簇。 图7 船基数据传输与通信分簇结果 然后,应用船基数据传输与通信船舶的簇头选举算法。使用本文提出的FCM在各个簇中选举簇头,仿真结果如图8所示,其中,圆圈为选取的簇头,方形框为基站。 图8 船基数据传输与通信节点选取的簇头 最后,应用PSO算法对船舶数据传输的路径进行优化。仿真过程中,若基站在船舶的通信范围内,各船舶直接将数据传输给基站;如果基站不在其通信范围内,则通过本簇的簇头进行转发,同理如果基站在簇头的通信范围内,则直接将融合后的数据发给基站,否则利用其他簇头通过PSO路径优化算法将数据转发给基站,仿真参数如表2所示。 表2 簇头数据传输参数 船舶在初始位置时,簇头1到基站的最优路径为1-2-基站,路径如图9所示。 图9 初始时刻最佳传输路径 经过一段时间后,所有船舶的位置发生了变化,即相应的最优数据传输路径也发生了变化,此时,簇头1到基站的路径发生了变化,为1-4-基站,而未使用PSO进行路径优化的路径为1-2-基站,路经对比如图10所示。 从仿真结果可以看出,相比较于未优化路径长度为151.34 km,优化后的路径为140.83 km,经过PSO算法进行船舶数据传输路径优化后的路径明显缩短了,实现了远海观测数据的快速回传。 图10 优化前后最佳传输路径对比 本文主要先使用改进的FCM算法实现对所有船舶的分簇,在利用FIS选取最优簇头;然后建立基于位置信息的船舶通信组网方式;最后通过PSO算法对船舶的数据传输路径进行优化,实现海洋观测数据的快速回传。本文所提方法良好的解决了数据传输与通信算法存在时延大、数据传输功率低等不足等问题,具备良好的工程使用价值。2 船舶编队通信组网方式
3 基于PSO的船舶通信网络数据传输路径优化
4 仿真实验
5 结语