王栽毅， 楊 照

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

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

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

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

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

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

(1)

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

(2)

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

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

1.1 船基數據傳輸與通信船舶的簇頭選舉

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

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

模糊規(guī)則的設計原則為：如果速度適中、加速度適中、距離簇中心點近，則該船舶成為簇頭的機會非常大。本文根據以上情況和基本經驗制定了3×3×3=27條模糊規(guī)則，使用三角隸屬函數表示模糊集的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所示。

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

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

圖1 船舶到簇中心距離及隸屬函數

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

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

圖3 簇成員加入流程圖

如果其中的一個成員離開CH1的通信范圍后，又不在其他簇內，則變?yōu)楣铝⒋?，在Tw內，又回到CH1的通信范圍內，因此又成為CH1的成員。若經過Tw后，又離開了CH1的通信范圍，此船舶就真正離開了此簇，變?yōu)楣铝⒋埃鞒虉D如圖4所示。

圖4 簇成員離開流程圖

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

2βR

(3)

首先，簇頭需通過原來的通信范圍R播送簇在分配的消息和新規(guī)定的通信范圍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 簇成員融合流程圖

2 船舶編隊通信組網方式

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

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

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

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

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

PSO算法是人工智能領域的一種基于群體的優(yōu)化算法，群體中的每一個個體都當作是問題的一個解，每個個體都有自己的速度，然后按照自己的速度飛行并搜索飛行過程中的最好位置，整個群體同樣尋找整個群體的最好位置，經過群體和自己的最好位置不斷調整自己的方向和速度，經過不斷的變化，找到最后最好的位置。每個個體的更新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為最大迭代次數。

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

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

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

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

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

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

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

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

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

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

(9) 根據輸出的每個個體的gbest求數據傳輸的最優(yōu)路徑。

4 仿真實驗

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

表1 船舶數據傳輸仿真參數

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

圖7 船基數據傳輸與通信分簇結果

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

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

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

表2 簇頭數據傳輸參數

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

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

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

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

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

5 結語

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