船聯(lián)網(wǎng)智能數(shù)據(jù)傳輸與通信算法研究?

王栽毅， 楊 照

(1. 中國(guó)海洋大學(xué)信息科學(xué)與工程學(xué)院， 山東 青島 266100；2.青島海洋科學(xué)與技術(shù)試點(diǎn)國(guó)家實(shí)驗(yàn)室， 山東 青島 266237)

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

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

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

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

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

(1)

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

(2)

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

迭代計(jì)算，當(dāng)選取的聚類中心誤差小于φ時(shí)，停止迭代，獲得各節(jié)點(diǎn)關(guān)于每個(gè)聚類中心的隸屬度和聚類中心坐標(biāo)。

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

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

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

模糊規(guī)則的設(shè)計(jì)原則為：如果速度適中、加速度適中、距離簇中心點(diǎn)近，則該船舶成為簇頭的機(jī)會(huì)非常大。本文根據(jù)以上情況和基本經(jīng)驗(yàn)制定了3×3×3=27條模糊規(guī)則，使用三角隸屬函數(shù)表示模糊集的Adequate，使用梯度隸屬函數(shù)表示Near、Far、Fast的Slow。其中，船舶到簇中心的距離用0～50 km,依據(jù)其大小表示距離到簇中心的遠(yuǎn)近，Near用梯度隸屬函數(shù)來(lái)表示，范圍為[-18，-5，5，18],Adequate用三角隸屬函數(shù)表示，范圍為[5，25，45],far用梯度函數(shù)表示，范圍為[30，45，55，70]；船舶自身的加速度的絕對(duì)值用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]；每個(gè)船舶的速度用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é)點(diǎn)分簇流程

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

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

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

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

圖3 簇成員加入流程圖

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

圖4 簇成員離開(kāi)流程圖

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

2βR

(3)

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

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

圖5 簇成員融合流程圖

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

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

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

圖6 基于位置和速度的TDMA時(shí)隙分配

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

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

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

(4)

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

慣性權(quán)重w表示為：

(5)

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

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

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

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

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

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

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

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

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

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

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

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

4 仿真實(shí)驗(yàn)

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

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

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

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

然后，應(yīng)用船基數(shù)據(jù)傳輸與通信船舶的簇頭選舉算法。使用本文提出的FCM在各個(gè)簇中選舉簇頭，仿真結(jié)果如圖8所示，其中，圓圈為選取的簇頭，方形框?yàn)榛尽?/p>

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

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

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

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

圖9 初始時(shí)刻最佳傳輸路徑

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

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

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

5 結(jié)語(yǔ)

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