王栽毅， 楊 照

(1. 中國海洋大學信息科學與工程學院， 山東 青島 266100；2.青島海洋科學與技術試點國家實驗室， 山東 青島 266237)

近年來，許多研究者應用分簇算法來提高數(shù)據(jù)傳輸?shù)男阅?。分簇算法在無線傳感器中有比較深入的研究，文獻[1-2]致力研究延長網(wǎng)絡的生命周期，這與船聯(lián)網(wǎng)分簇的目標一致[3]，但在船聯(lián)網(wǎng)中船舶并沒有能量限制，在分簇中無需考慮能量問題；其次，在船聯(lián)網(wǎng)中船舶處于快速移動的狀態(tài)，網(wǎng)絡拓撲結(jié)構在不斷的變化，而傳統(tǒng)的分簇算法并不能根據(jù)網(wǎng)絡拓撲結(jié)構變化來自適應調(diào)整分簇；最后，傳統(tǒng)的分簇算法主要從能量和路由兩方面來考慮其發(fā)射功率，進而決定簇的大小，分簇算法往往和路由協(xié)議相結(jié)合，而在船聯(lián)網(wǎng)中，簇的大小是由每個時間幀中所劃分的時隙數(shù)決定的，其中時間幀的長短受消息時延要求的制約，時隙即為網(wǎng)絡中的傳輸時間被劃分為一個個時間間隔，每個時間間隔作為一個時隙，每個時隙作為信道資源提供給網(wǎng)絡中的節(jié)點用于傳輸信息。因此針對傳統(tǒng)的分簇算法在船聯(lián)網(wǎng)中的缺陷，本文利用改進的模糊C均值(FCM)[4-6]算法進行分簇，解決船舶的拓撲結(jié)構不斷變化的問題。

目前的數(shù)據(jù)鏈路中，船舶編隊通信組網(wǎng)方式大多以時分多址(TDMA)[7-13]作為接入算法，TDMA擁有簡捷、高效的優(yōu)點，與此同時也擁有系統(tǒng)固定，傳輸開銷大等劣勢。TDMA被廣泛用作有效的通信手段。由于TDMA組網(wǎng)的拓撲變化適合船聯(lián)網(wǎng)中船舶的拓撲變化快速的特點，因此，TDMA廣泛作為船聯(lián)網(wǎng)的組網(wǎng)方式。但當兩個彼此遠離的簇，在分配時隙時，有兩個船舶占用了相同的時隙，當隨著速度差的原因，兩船進入彼此的通信范圍，占用相同時隙的船舶在進行消息傳輸時就會發(fā)生碰撞，在簇頭沒有重新分配的情況下，會一直碰撞，直到兩個簇駛離彼此的通信范圍，碰撞才會消失。因此，在進行時隙分配時，合理的分配時隙，能有效的降低消息碰撞率，提高信道的利用率。根據(jù)以上時隙碰撞情況，本文提出了利用船舶的速度及位置進行時隙分配的策略。同時，本文提出基于粒子群(Particle Swarm Optimization， PSO)算法的數(shù)據(jù)傳輸路徑優(yōu)化算法，以實現(xiàn)海洋觀測數(shù)據(jù)的快速回傳。

1 船基數(shù)據(jù)傳輸與通信節(jié)點分簇

為改進傳統(tǒng)的分簇算法在船聯(lián)網(wǎng)中的缺陷，本文通過改進的FCM算法，將時隙數(shù)量的制約引入到船聯(lián)網(wǎng)中。首先把規(guī)定范圍內(nèi)擁有最多鄰居節(jié)點的點作為第一個聚類中心點。再根據(jù)到前一個聚類中心的距離和自身鄰居節(jié)點的數(shù)量，使用歸一化加權方法把距離前一個聚類中心最遠和鄰居節(jié)點數(shù)量最多的點作為下一個聚類中心。以此方法得到K個聚類中心vj(j=1，2，…，K)，其中K是根據(jù)海域的范圍和船舶的數(shù)量進行確定的。設定迭代的收斂條件φ。

利用公式(1)計算各點到各聚類中心距離的隸屬度uij。

(1)

式中：uij表示第i個船舶對第j個簇的隸屬度；xi為各船舶的坐標。如果選出的點誤差大于φ，使用公式(2)重新計算新的中心點。

(2)

式中m表示模糊加權指數(shù)，通常情況下其值為2。

迭代計算，當選取的聚類中心誤差小于φ時，停止迭代，獲得各節(jié)點關于每個聚類中心的隸屬度和聚類中心坐標。

1.1 船基數(shù)據(jù)傳輸與通信船舶的簇頭選舉

因為船聯(lián)網(wǎng)中的船舶處于變化快速的狀態(tài)，網(wǎng)絡拓撲結(jié)構也在不斷的變化，因此對簇需要進行維護，在進行維護的同時又需要重新選擇每個簇的簇頭，這就需要選擇發(fā)生變化少的節(jié)點當作簇頭，從而減少維護過程中帶來的開銷。本文的簇頭的選舉綜合考慮船舶的速度、加速度以及位置這些因素，通過模糊邏輯系統(tǒng)選取最優(yōu)簇頭，實現(xiàn)各船舶的自適應分簇，仿真驗證了該方法的有效性與可行性(具體參數(shù)及隸屬函數(shù)見圖1和2)。

船舶節(jié)點的位置和速度是選取簇頭的重要因素，本文使用FIS(Fuzzy logic system)[14]選取簇頭考慮三方面輸入?yún)?shù)：船舶的速度、船舶到簇中心的距離和船舶自身的加速度。其中表示船舶到簇中心的距離的語言變量分為三個層次：Near、Adequate、Far，表示船舶速度和加速度語言變量Fast、Adequate、Slow。船舶使用分簇算法選取簇頭的可能被列為7種情況：Rather Small、Very Small、Small、Middle、Large、Very Large和Rather Large。

模糊規(guī)則的設計原則為：如果速度適中、加速度適中、距離簇中心點近，則該船舶成為簇頭的機會非常大。本文根據(jù)以上情況和基本經(jīng)驗制定了3×3×3=27條模糊規(guī)則，使用三角隸屬函數(shù)表示模糊集的Adequate，使用梯度隸屬函數(shù)表示Near、Far、Fast的Slow。其中，船舶到簇中心的距離用0～50 km,依據(jù)其大小表示距離到簇中心的遠近，Near用梯度隸屬函數(shù)來表示，范圍為[-18，-5，5，18],Adequate用三角隸屬函數(shù)表示，范圍為[5，25，45],far用梯度函數(shù)表示，范圍為[30，45，55，70]；船舶自身的加速度的絕對值用0～5 kn/min表示,low用梯度隸屬函數(shù)表示，范圍為[-1.5，-0.7，0.7，1.5]，Med用三角函數(shù)表示，范圍為[0.5，2.5，4.5]，High用梯度隸屬函數(shù)表示，范圍為[3，4.3，5.7，7]；每個船舶的速度用0～30 kn表示，low用梯度隸屬函數(shù)表示，范圍為[-10，-3，3，10]，Med用三角函數(shù)表示，范圍為[3，18，25]，High用梯度隸屬函數(shù)表示，范圍為[18，25，35，42]。各參數(shù)的隸屬函數(shù)如圖1和2所示。

1.2 船基數(shù)據(jù)傳輸與通信節(jié)點分簇流程

首先根據(jù)船舶的數(shù)量以及海域的范圍，確定大約將船舶分為幾簇；然后利用改進的FCM算法對整個海域內(nèi)的船舶進行分簇，利用上文提出的簇頭選舉算法為每個簇選舉最優(yōu)的簇頭，其他不是簇頭的船舶根據(jù)通信范圍的遠近，選定所屬的簇；最后考慮簇的加入與離開、簇的融合與分離，決定是否重新分簇。

圖1 船舶到簇中心距離及隸屬函數(shù)

圖2 船舶速度及模糊規(guī)則隸屬函數(shù)

1.2.1 簇成員的駛?cè)肱c駛離 船聯(lián)網(wǎng)中實施分簇算法，經(jīng)常發(fā)生的變化就是船舶的駛?cè)肱c駛離引起的拓撲變化。當孤立的船舶即沒有鄰居節(jié)點的船舶，進入一個簇頭(CH1)的通信范圍時，此孤立船舶就會收到CH1的信息，此孤立船舶便會向CH1發(fā)送請求加入的信息，CH1收到請求信息后，根據(jù)MAC層時隙的數(shù)量判斷其是否可以加入，若受延時的要求不能加入此簇時，就發(fā)送拒絕加入的信息，否則進入等待期。等待期時長為Tw，等待Tw時長以后，如果依然在CH1的通信范圍內(nèi)，該孤立節(jié)點就成功加入此簇，成為其中的一員，流程圖如圖3所示。

圖3 簇成員加入流程圖

如果其中的一個成員離開CH1的通信范圍后，又不在其他簇內(nèi)，則變?yōu)楣铝⒋埃赥w內(nèi)，又回到CH1的通信范圍內(nèi)，因此又成為CH1的成員。若經(jīng)過Tw后，又離開了CH1的通信范圍，此船舶就真正離開了此簇，變?yōu)楣铝⒋?，流程圖如圖4所示。

圖4 簇成員離開流程圖

1.2.2 簇成員的再次分配 簇成員的再次分配主要包含兩種情況：一種是經(jīng)過航道分叉口時，一些船舶繼續(xù)按照原先的航道，另一些船舶進入其他的航道，這樣該簇就變?yōu)閮蓚€簇；另一種可能是伴隨著船舶數(shù)量的增加，受MAC層時延的要求， 該簇不能容納此時簇內(nèi)所有的船舶，就要分出新的簇。航道分叉比較容易，即以前的簇頭依然不變，在分出的簇中依然擔任簇頭；而另外一種是依據(jù)簇成員的加入方法加入其它簇中，如果一些船舶都沒在其他簇的通信范圍內(nèi)，則這些船舶形成新的簇，在使用分簇算法選出新的簇頭。在分簇算法中，MAC層的延時受時隙數(shù)量的制，根據(jù)MAC層時隙的數(shù)量決定簇成員的最大數(shù)量wmax時，如果簇內(nèi)成員達到wmax，若繼續(xù)有新的節(jié)點加入，此時的簇不能容納所有的簇成員，該簇的簇頭便依據(jù)船密度β重新規(guī)定船舶的通信范圍R，使新的船舶通信范圍R′滿足

2βR

(3)

首先，簇頭需通過原來的通信范圍R播送簇在分配的消息和新規(guī)定的通信范圍R′，然后，原先想要加入該簇的成員收到消息后將其通信范圍改為R′，最后，根據(jù)新的通信范圍R′，利用分簇算法以及簇頭選舉算法，形成新的簇。

1.2.3 簇成員的融合 如果兩個簇的簇頭可以互相進行通信且簇內(nèi)的數(shù)量較少，就需要進行簇成員的融合。進行簇融合的原理為成員少的簇加入成員多的簇內(nèi)，在滿足MAC時延要求和所有成員都在簇頭的通信范圍內(nèi)時，就融合為一個，否則將沒有融入的其他成員形成另外一個簇。比如在簇A中，擁有1、2、3三個簇成員，而在簇B中包括1、2、3、4四個簇成員。因為A的成員少于B，所以在B通信范圍內(nèi)且滿足MAC時延要求下，A成員全部加入B中，如果B不能容納所有A中的船舶，則B通知A將剩余的船舶形成新的簇，并選取新的簇頭，成為新簇，簇融合過程如圖5所示。

圖5 簇成員融合流程圖

2 船舶編隊通信組網(wǎng)方式

根據(jù)以上時隙碰撞情況，本文提出了利用船舶的速度及位置進行時隙分配的策略，具體流程為：

在其中一個簇頭為CHM，簇成員數(shù)量為n的簇M中進行時隙分配時，首先利用簇頭選舉算法選舉出本簇中的簇頭，然后給定一個速度值，區(qū)分本簇中船舶的快慢，根據(jù)給定的速度值，將本簇中的船舶分為兩種情況，一種是快速船舶，快速船舶在1、3、5…這樣的奇數(shù)號時隙中根據(jù)位置的前后占用時隙，也就是位置靠前的船舶占用的奇數(shù)序號越小。同理，慢速船舶也根據(jù)位置和速度在偶數(shù)號中占用時隙。比如在快速船舶中，在本簇最前邊的節(jié)點預約1號，后邊相應的預約3、5、7等。當某一種情況下船舶數(shù)大于該情況下的時隙數(shù)時，可以占用對方的時隙。改進后的時隙分配如圖6所示。

圖6 基于位置和速度的TDMA時隙分配

3 基于PSO的船舶通信網(wǎng)絡數(shù)據(jù)傳輸路徑優(yōu)化

簇內(nèi)成員將數(shù)據(jù)傳輸給簇頭，簇頭進行數(shù)據(jù)融合，然后簇頭之間使用PSO[15]路徑優(yōu)化，用最短的路徑將數(shù)據(jù)傳輸給基站。

PSO算法是人工智能領域的一種基于群體的優(yōu)化算法，群體中的每一個個體都當作是問題的一個解，每個個體都有自己的速度，然后按照自己的速度飛行并搜索飛行過程中的最好位置，整個群體同樣尋找整個群體的最好位置，經(jīng)過群體和自己的最好位置不斷調(diào)整自己的方向和速度，經(jīng)過不斷的變化，找到最后最好的位置。每個個體的更新X和V公式為：

(4)

式中：Vid(j)表示個體i在第j輪中的速度；Xid(j)表示個體i在第j輪中的位置；pbest表示粒子當前的最佳位置；gbest表示粒子群當前的最佳位置；w代表慣性權重；c1、c2為學習因子；r1、r2表示0～1之間的隨機數(shù)。

慣性權重w表示為：

(5)

式中：wmax表示慣性權重w的最大值；wmin表示慣性權重w的最小值；t代表當前的迭代次數(shù)；T為最大迭代次數(shù)。

在本文中，首先利用分簇算法選取簇頭，它們組成船舶通信網(wǎng)絡數(shù)據(jù)傳輸?shù)暮蜻x節(jié)點集合，然后根據(jù)節(jié)點通信能力選擇船舶通信網(wǎng)絡數(shù)據(jù)傳輸下一跳節(jié)點，最后利用PSO算法優(yōu)化選中的下一個通信節(jié)點，得到其數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑。

通過PSO算法得到船舶進行數(shù)據(jù)傳輸最優(yōu)路徑的流程為:

(1) 初始化PSO各個參數(shù)，即wmax、wmin、c1、c2、T以及n；

(2) 利用簇頭選舉算法得到最優(yōu)簇頭的位置；

(3) 初始化所有船舶的位置X和速度V，其中每個船舶代表一個個體；

(4) 初始化每個個體的pbest和群體的gbest；

(5) 計算每個個體的適應度值，并判斷是不是符合約束前提，如果不符合就重新搜索；

(6) 更新每個個體的pbest和群體的gbest；

(7) 依據(jù)公式(5)更新慣w，并利用(4)更新每個個體的X和V；

(8) 根據(jù)t判斷是不是到達了T，如果是，則得到群體的gbest，否則繼轉(zhuǎn)到(4)，繼續(xù)尋找gbest；

(9) 根據(jù)輸出的每個個體的gbest求數(shù)據(jù)傳輸?shù)淖顑?yōu)路徑。

4 仿真實驗

本文應用MATLAB軟件進行仿真實驗。每個船舶可以和通信范圍內(nèi)的所有船舶進行通信。在仿真期間，船只數(shù)目保持不變。使用PSO對簇頭、簇內(nèi)節(jié)點到基站的數(shù)據(jù)傳輸進行優(yōu)化，仿真參數(shù)如表1所示。

表1 船舶數(shù)據(jù)傳輸仿真參數(shù)

仿真環(huán)境下的方形海域內(nèi)，由一個基站，位置為(0，60 km)和100艘船組成，仿真大范圍為120 km×120 km。假設每艘船的通信范圍為30 km。應用本文所提船基數(shù)據(jù)傳輸與通信節(jié)點分簇算法，對實驗場景下的船舶目標進行分簇處理，仿真結(jié)果如圖7所示。容易看出，算法將整個海域范圍分為4簇。

圖7 船基數(shù)據(jù)傳輸與通信分簇結(jié)果

然后，應用船基數(shù)據(jù)傳輸與通信船舶的簇頭選舉算法。使用本文提出的FCM在各個簇中選舉簇頭，仿真結(jié)果如圖8所示，其中，圓圈為選取的簇頭，方形框為基站。

圖8 船基數(shù)據(jù)傳輸與通信節(jié)點選取的簇頭

最后，應用PSO算法對船舶數(shù)據(jù)傳輸?shù)穆窂竭M行優(yōu)化。仿真過程中，若基站在船舶的通信范圍內(nèi)，各船舶直接將數(shù)據(jù)傳輸給基站；如果基站不在其通信范圍內(nèi)，則通過本簇的簇頭進行轉(zhuǎn)發(fā)，同理如果基站在簇頭的通信范圍內(nèi)，則直接將融合后的數(shù)據(jù)發(fā)給基站，否則利用其他簇頭通過PSO路徑優(yōu)化算法將數(shù)據(jù)轉(zhuǎn)發(fā)給基站，仿真參數(shù)如表2所示。

表2 簇頭數(shù)據(jù)傳輸參數(shù)

船舶在初始位置時，簇頭1到基站的最優(yōu)路徑為1-2-基站，路徑如圖9所示。

圖9 初始時刻最佳傳輸路徑

經(jīng)過一段時間后，所有船舶的位置發(fā)生了變化，即相應的最優(yōu)數(shù)據(jù)傳輸路徑也發(fā)生了變化，此時，簇頭1到基站的路徑發(fā)生了變化，為1-4-基站，而未使用PSO進行路徑優(yōu)化的路徑為1-2-基站，路經(jīng)對比如圖10所示。

從仿真結(jié)果可以看出，相比較于未優(yōu)化路徑長度為151.34 km，優(yōu)化后的路徑為140.83 km，經(jīng)過PSO算法進行船舶數(shù)據(jù)傳輸路徑優(yōu)化后的路徑明顯縮短了，實現(xiàn)了遠海觀測數(shù)據(jù)的快速回傳。

圖10 優(yōu)化前后最佳傳輸路徑對比

5 結(jié)語

本文主要先使用改進的FCM算法實現(xiàn)對所有船舶的分簇，在利用FIS選取最優(yōu)簇頭；然后建立基于位置信息的船舶通信組網(wǎng)方式；最后通過PSO算法對船舶的數(shù)據(jù)傳輸路徑進行優(yōu)化，實現(xiàn)海洋觀測數(shù)據(jù)的快速回傳。本文所提方法良好的解決了數(shù)據(jù)傳輸與通信算法存在時延大、數(shù)據(jù)傳輸功率低等不足等問題，具備良好的工程使用價值。