# Belief Propagation-Based Cognitive Routing in Maritime Ad Hoc Networks

Authors: Huma Ghafoor; Youngtae Noh; Insoo Koo
Journal: International Journal of Distributed Sensor Networks
 (2016)

---

## Abstract

Cognitive routing for maritime wireless ad hoc networks is proposed in this paper to find a stable path between source and destination. This is ship-to-ship communication where two ships can communicate when they not only have consensus on a common idle channel but also are in the transmission range of each other. We apply belief propagation algorithm for collaborative spectrum sensing. Every user (ship) exchanges its local decisions with its neighbors to compute the final belief about the state of the channel. These beliefs are applied for estimating the link duration for total number of hops between source and destination. Then, a path is selected which maximizes the path duration among all the paths in the network to reach the destination. We apply both flood-based and geographical routing protocols to find a route between source and destination for different scenarios. We simulate our scheme for different ocean settings and evaluate path durations for different number of ships. The results report a significant increase in path duration as the number of nodes increases in the network. In addition, we verify that path duration increases with an increase in probability of primary user being idle via extensive simulations. Hence, our scheme provides stable path selection for communication among users onboard.


---

## Body

## 1. Introduction

Maritime communications play an essential role in providing variety of services to users aboard. These services include ship navigation, ship traffic management, location, and all other entertainment-related information for passengers [1]. The demand for safe and stable maritime communications has been increased due to the increase in number of marine users. Existing maritime communication systems are based on high frequency (HF), very high frequency (VHF), and ultrahigh frequency (UHF) radios which are currently insufficient for growing maritime requirements [2]. To fulfill the increasing needs of maritime communication systems, licensed spectrum can be used opportunistically by unlicensed users while keeping the licensed users safe [3]. A stable wireless communication link is essential for maritime communications with the availability of spectrum. Therefore, a new technique is required to provide stable link for cognitive maritime communications by ensuring cooperation among marine users.Various routing techniques have been proposed to provide stable link in mobile ad hoc networks (MANETs) and vehicular ad hoc networks (VANETs). These routing techniques cannot be directly applied in maritime networks due to rough sea surface. Identical to these networks, routing in cognitive maritime networks is also important for ensuring connectivity among maritime users. In maritime networks, ship-to-ship communication is continuously perturbed by sea waves that cause fluctuations in the signal strength resulting in fragile communication links; therefore, establishing a stable link in sea environment is a challenging task. Similarly, because of the movement of sea surface channel statistics also change continuously [4]. Furthermore, due to increasing demands of seafaring internet users, bandwidth allocations have been congested; hence, it is difficult for maritime ad hoc network to find dedicated spectrum [5]. Cognitive radio (CR) seems to be a technology to alleviate this issue in ship-to-ship communication. Ships are allowed to opportunistically sense the spectrum, provided that they ensure that the operation of primary user (PU) is not affected. Like VANETs, the implementation of CR network is different from generic CR networks due to dynamic nature of ships; therefore, cooperation among maritime users must be considered. Moreover, the ongoing ship-to-ship communication can be affected by PU activity and random sea surface which may cause the established routes to be invalid.The following are the key contributions of the paper:(i)
A novel scheme for cognitive maritime multihop ad hoc network is proposed to find a stable path between source and destination based on belief propagation (BP) algorithm. BP algorithm [6, 7] is an iterative message passing algorithm which can be applied in maritime communications for collaborative spectrum sensing. This algorithm allows each ship to send the local sensing results obtained from energy detection scheme to all the neighbors in its communication range. Then, each ship combines its belief with the beliefs of all its neighbors to make a final belief about the existence of PU. Ships update each other periodically about their current positions, and theKalman filter is used to predict their future positions.(ii)
Finally, the best stable path is selected using two well-known routing protocols by finding minimum link duration between source and destination with their beliefs: one is flood-based routing protocol named ad hoc on-demand distance vector (AODV) [8] and the other is geographical routing protocol named greedy perimeter stateless routing (GPSR) [9].The remaining paper is organized as follows. Related work is presented in Section2. In Section 3, we propose the belief propagation-based ad hoc routing algorithm. Section 4 demonstrates performance results, and, finally, Section 5 concludes the paper.


## 2. Related Work

Spectrum sensing in cognitive maritime networks is in its early stages in comparison with cognitive radio networks on land. The main objective of spectrum sensing in cognitive maritime networks is similar to generic cognitive radio networks to provide spectrum opportunities to unlicensed (cognitive) users by keeping PU activity safe. Spectrum sensing is mainly classified into three categories in literature: energy detection, matched filter detection, and feature detection. All these classes are known for distinct characteristics and each one can be implemented in any scenario according to network requirements to enhance spectrum accuracy [10]. Energy detection is the simplest technique that has short sensing time and it is useful when little or no knowledge of PU signal is available. The matched filter detection requires a priori knowledge about the waveform of PU signal whereas the feature detection is computationally complex and requires long sensing time as compared with the other two [5]. Also, energy detection is a relevant scheme for CR-VANETs because of its capability to be adapted in all sorts of deterministic signals [11]. As ships moving at sea and vehicles in traffic are more or less related to each other, we can say that cognitive maritime networks are analogous to CR-VANETs. Therefore, in this work, we use energy detection scheme for spectrum sensing.Ejaz et al. [5] are the first to consider spectrum sensing in cognitive maritime networks. They investigated an entropy-based detection to offset the sea state effects in maritime cognitive radio network by using optimal number of samples to calculate the entropy of sensed signal as an information measure of PU presence/absence. Their results showed better performance for higher sea states with optimal number of samples but these results still do not satisfy the constraints of probability of detection and false alarm. Tang et al. [12] introduced the idea of cognitive radio to automatic identification system (AIS) for the first time by sensing white spaces based on energy detection scheme without interfering with AIS services. They opened new doors for spectrum sensing in cognitive maritime VHF networks.Due to rough sea surface, routing in cognitive maritime networks is more challenging as compared to conventional cognitive routing protocols on land. Apart from distinct challenging environment in cognitive maritime networks, maritime communication is analogous to vehicular communication; therefore, few routing protocols proposed for VANETs can be applied in maritime environment. But the performance of these protocols in maritime networks is poor than that in vehicular networks because links in marine environment may break more frequently due to constant movement of sea surface. We apply our scheme for both flood-based and geographical routing protocols to measure the maximum duration of a route that will remain active in marine networks for communication between source and destination. A few routing protocols that have been proposed in literature are listed here.Kong et al. [13] proposed an aggregated-path routing approach in maritime multihop wireless networks. The purpose is to avoid retransmissions due to long bad duration of links in maritime communications. They evaluated their routing approach using one source and one destination for end-to-end connection. Their simulated results showed that aggregated-path routing is better than traditional single-path routing. Maritime two-state (MTS) routing protocol [1] is proposed for maritime multihop wireless networks. All nodes (ships) in the network can be in either of two states: beaconing or predicting. Beaconing state is responsible for exchanging routing information with the neighboring nodes while predicting state predicts the future location of each ship. Their results showed better performance in terms of bandwidth utilization for coverage area of up to 10 km. Four different MANET routing protocols have been implemented in [14] using marine environment for the coverage range of up to 40 km. A comparison is made for these protocols showing their advantages and disadvantages. These protocols have limitations in marine environment, which can be sparse in some locations and dense in others. Among these MANET protocols, AOMDV is found to be efficient for ship-to-ship communication.All of these existing routing protocols for maritime ad hoc networks do not consider spectrum scarcity issues caused by congested bandwidth allocations. Due to increasing demand of marine users, spectrum is found to be insufficient to meet the needs of maritime communications. As the sea surface changes constantly, the links may break frequently; therefore, estimation of path duration is essential for maritime ad hoc networks. Accordingly, selection of routing protocol plays an important role in estimation of path duration. For that reason, spectrum sensing and routing are important to be considered together while implementing a maritime ad hoc network. To enhance path stability in the network, we are considering both spectrum scarcity and routing issues together. Our motive is to provide a stable path for communication between source and destination in marine environment by jointly selecting channel and relay. This work proposes a cognitive routing protocol for maritime ad hoc networks based on collaborative spectrum sensing scheme to estimate the path duration for marine communications.


## 3. System Model and the Proposed Scheme

We consider a cognitive maritime ad hoc network withI ships, which is represented by a graph where each node represents a ship and each edge is a communication link between two ships as shown in Figure 1. A cognitive routing technique is proposed by considering the movement of ships in marine environment. The purpose of using cognitive principles in maritime ad hoc network is to increase the spectrum opportunities for ship-to-ship communication. This is a spectrum-aware routing scheme in which collaborative spectrum sensing is done by using BP algorithm, and then a route is selected based on both AODV and GPSR routing protocols. Our goal is to find a stable path among all the paths between source and destination which maximizes the path duration to facilitate communication between different ships. This path is calculated by combining beliefs and link durations for total number of hops between source and destination.Figure 1
Cognitive maritime multihop ad hoc network.Ships are assumed to be equipped with GPS receiver to get its current location. All ships periodically update current geographic positions of their neighborhood ships and further predict their future positions using theKalman filter, which will be described in Section 3.2.1. This helps the querying node (e.g., source node in Figure 1) to find the best relay node that makes stable path between source and destination by considering the current and future positions of all the nodes in its communication range. Primary users are assumed to be sited close to seashore as shown in Figure 1. We define PUs as incumbent users that provide services for transmission of important information like vessel navigation, disaster rescue, weather broadcasting, and so on. We also assume that there is plenty of white space (WS) available at sea as analyzed in [4] and we divide the TV band into M channels where PU activity is modeled as exponential on/off activity pattern. Spectrum sensing is done by energy detection scheme. Each ship senses the spectrum using a binary hypothesis model which is defined as follows:(1)xit=nit,H0sit+nit,H1,where i=1,…,I, sit is a complex signal received from PU, and nit is the complex additive white Gaussian noise (AWGN). Therefore, in discrete domain, the energy based test statistic is given as follows:(2)xEi=∑n=1Nxinxi~n,where N is the time-bandwidth product and xi~n is the conjugate signal of xin.Generation of sea environment is a challenging task. Pierson Jr. and Moskowitz [15] describe the movement of sea waves by dividing sea states into 10 levels. Sea state is a measure of sea surface movement using parameters of significant wave height, wave period, and wave length. Each sea state has its own wave height, average period, and average wave length. Sea movement changes the orientation of antenna which affects the received signal power. We assume that all antennas are omnidirectional in the horizontal plane, even though, due to the movement of sea surface, tilting of antenna masts causes change in antenna gain which affects the received signal power. Therefore, different ships experience different signal-to-noise ratio (SNR) which is calculated as follows:(3)γi=PRsiNoW,where NoW is the total noise power and PRsi is the received power calculated as follows:(4)PRsi=PT-PL.PT and PL are the transmitted power and path loss, respectively. For maritime environment, the path loss PL is the function of frequency f and sea surface height h which is defined by [16] as follows:(5)PLh,f=PLdo+100.498log10⁡f+0.793h+2log10⁡ddo+Xf.PLdo is the path loss measured at reference distance from transmitter and Xf is a Gaussian random variable with zero mean and standard deviation given as σf=0.157f+0.405×h.The proposed method is twofold: first, the selection of free channel where collaborative spectrum sensing is done using belief propagation algorithm by exchanging the local decisions between neighboring ships to make a final belief and, second, the selection of a stable path by finding minimum link duration between source and destination with their beliefs which in turn maximizes the path duration. In the following sections, we discuss these two parts thoroughly.


### 3.1. Channel Selection Scheme Based on Belief Propagation Algorithm

We consider cognitive ship-to-ship communication in which all nodes are moving ships. Each ship periodically senses the spectrum and stores the result in its sensing table. BP [17] is an iterative algorithm in which messages are exchanged to approximate the marginal probabilities (i.e., the beliefs). The first step for BP algorithm is to calculate the local information which is equal to thea posterior probability. We use energy detection scheme for local sensing as discussed in (1) and (2) above. For each ship i, thea posterior probability is calculated as follows:(6)φifHh=PHh∣xi=Pxi∣HhPHhPxi,where f∈M,  Pxi∣Hh is the probability density function of normally distributed complex random variable x conditioned on Hh, h=0,1, that is, ∫fx∣Hhx∣Hhdx, Pxi is the probability density function of uniformly distributed random variable x, and PHh is a prior probability which is assumed to be constant for all ships. Each ship exchanges its local sensing results with all its neighboring ships and updates its sensing table according to BP algorithm. Two ships i and j in the communication range of each other exchange their messages as follows:(7)μijfHj=wi∑HiψijfHi,HjφifHi∏k∈Ni-jμkifHi.μijfHj describes belief about the state of ship j estimated by ship i. wi in (7) is the weighting factor, k belongs to the neighbors of i only, and ψijfHi,Hj is a compatibility function which depends on the correlation between states Hi and Hj. The compatibility function is defined as follows:(8)ψijfHi,Hj=ηifHi=Hj1-ηifHi≠Hj.Finally, the belief of each ship is computed as follows:(9)bifHi=wiφifHi∏k∈NiμkifHi.On the basis of these beliefs, each ship makes the final decision about the current channel in which it is moving on as follows:(10)Dif=H0ifbifH0>bifH1H1ifbifH0<bifH1.An example illustrating how three ships exchange their individual observations resulting from energy detection scheme using belief propagation algorithm and then make the final belief about state (idle/busy) of channel is shown in Figure 2.Figure 2
An example illustrating belief propagation algorithm for collaborative spectrum sensing.


### 3.2. Routing Scheme Based on Estimation of Path Duration

The estimation of path duration in cognitive maritime communications makes the routing efficient by exchanging geographic positions and beliefs of each ship with their neighboring ships. In this subsection, we explain how stable path is calculated by using beliefs obtained in the previous subsection. As this is cognitive ship-to-ship communication, the position of ships and channel condition are changing continuously with the movement of sea. All ships send messages to their neighboring ships about their positions and beliefs which are considered as additional entries in a beacon message. Therefore, each ship can calculate its distance from its immediate neighbors. We use theKalman filter to predict future positions of all the ships. We will discuss in Section 3.2.1 how we estimate the future values of position and velocity of ships by using theKalman filter algorithm.The estimation of path duration is helpful in selecting the path to transfer data packets from source to destination. An efficient routing protocol is required to estimate the path duration considering the challenges faced by marine environment. A few of existing routing protocols for terrestrial environment have been implemented in marine environment [14] and also some new routing protocols have been proposed for marine communications [1, 13]. We are concerned with the estimation of path duration to select a stable route for ship-to-ship communication as maritime link might be blocked by various propagation impairments. Therefore, we use both flood-based and geographical routing protocols to check their validity among challenges of maritime environment.To find a stable path between source and destination using AODV [8], aroute request (RREQ) is sent by the source node to all the neighbors in its communication range moving towards the destination. It is noteworthy that beliefs are updated as an additional entry among all the fields of RREQ. The RREQ passes through several nodes forming active links and then finally reaches the destination. Once the RREQ reaches the destination, the destination sends back aroute reply (RREP) to the source node. Hence, the stable path is calculated by computing the minimum link duration among all the links between source and destination for the common free channels, while GPSR [9] uses greedy forwarding to select next hop in making links with the source node. Three basic entities are used in applying greedy forwarding: the position of querying node, the position of all neighbors, and position of destination. The principle says that the source node selects that neighbor node which is the closest to the destination. Again, we mention here that in selecting the next node using GPSR all nodes send their beliefs as an extra entity in beacon message. Figure 3 explains the comprehensive algorithm by showing how source/relay selects the next hop nodes and beliefs of free channels jointly to reach the destination and then chooses the final route which maximizes the path duration among all the paths.Figure 3
A flowchart representing proposed algorithm.Two ships which are in the transmission range of each other having at least a common free channel calculate their link duration as follows:(11)LDij=Lij·min⁡bifH0,bjfH0,where Lij is the estimated time for which the direct link between two nodes within the transmission range of each other is active and is calculated in the same way as proposed by Liu et al. [18]: (12)Lij=R∓dijV,where R is the transmission range of ship i, dij is the distance between ship i and ship j, and V is the velocity of the ships. We will explain with examples the evaluation of Lij in Section 4. Hence, the path duration between source and destination is calculated as follows:(13)PDp=min⁡LD1p,LD2p,…,LDThp,where Th is the total number of hops between source and destination, p is index for path between source and destination, and p is from 1,…,P. Finally, a route p^ is selected which maximizes path duration among all the paths p:(14)p^=arg⁡maxp^∈p⁡PDp.


#### 3.2.1.Kalman Filter Algorithm

As discussed in previous subsection, in order to make routing efficient by achieving a reasonable delay, we use aKalman filter in our proposed routing scheme to predict future positions of all ships. In this subsection, we briefly explain theKalman filter [19] algorithm. TheKalman filter has two vectors: state vector and measurement vector. The state vector consists of position Pt and velocity Vt of a ship; that is, ut=PtVt. The measurement vector is a measurement at time t. Two equations are used in this algorithm: a process equation and a measurement equation. The process equation predicts the future values of the ships at time t+1 and the measurement equation gives the observation value from the GPS. The process equation and measurement equation are defined by (15) and (16), respectively, as follows:(15)ut+1=Aut+εu,(16)zt=Hut+εz,where A and H are state transition and measurement matrices, respectively, εu is process noise, and εz is measurement noise. Both noises have a normal distribution with zero mean and a covariance matrix of Q and R, respectively.To measure the predicted and new values of moving ships, the algorithm is further divided into two steps: a prediction step and an update step. The prediction step predicts the state and covariance whereas the update step is a combination of predicted state and observation value. The predicted values are defined as follows:(17)u^t+1=Aut,Pt+1=APtAT+Q.And the new estimated values of each ship are defined as follows:(18)u^t+1∣t+1=u^t+1∣t+Kzt+1-Hu^t+1∣t,Pt+1∣t+1=Pt+1∣t-KR+HPt+1∣tHTKT,where K is theKalman gain calculated from(19)K=Pt+1tHTR+HPt+1tHT-1.Therefore, from the above equations, we can estimate the future values of position and velocity of ships by using theKalman filter algorithm.


## 3.1. Channel Selection Scheme Based on Belief Propagation Algorithm

We consider cognitive ship-to-ship communication in which all nodes are moving ships. Each ship periodically senses the spectrum and stores the result in its sensing table. BP [17] is an iterative algorithm in which messages are exchanged to approximate the marginal probabilities (i.e., the beliefs). The first step for BP algorithm is to calculate the local information which is equal to thea posterior probability. We use energy detection scheme for local sensing as discussed in (1) and (2) above. For each ship i, thea posterior probability is calculated as follows:(6)φifHh=PHh∣xi=Pxi∣HhPHhPxi,where f∈M,  Pxi∣Hh is the probability density function of normally distributed complex random variable x conditioned on Hh, h=0,1, that is, ∫fx∣Hhx∣Hhdx, Pxi is the probability density function of uniformly distributed random variable x, and PHh is a prior probability which is assumed to be constant for all ships. Each ship exchanges its local sensing results with all its neighboring ships and updates its sensing table according to BP algorithm. Two ships i and j in the communication range of each other exchange their messages as follows:(7)μijfHj=wi∑HiψijfHi,HjφifHi∏k∈Ni-jμkifHi.μijfHj describes belief about the state of ship j estimated by ship i. wi in (7) is the weighting factor, k belongs to the neighbors of i only, and ψijfHi,Hj is a compatibility function which depends on the correlation between states Hi and Hj. The compatibility function is defined as follows:(8)ψijfHi,Hj=ηifHi=Hj1-ηifHi≠Hj.Finally, the belief of each ship is computed as follows:(9)bifHi=wiφifHi∏k∈NiμkifHi.On the basis of these beliefs, each ship makes the final decision about the current channel in which it is moving on as follows:(10)Dif=H0ifbifH0>bifH1H1ifbifH0<bifH1.An example illustrating how three ships exchange their individual observations resulting from energy detection scheme using belief propagation algorithm and then make the final belief about state (idle/busy) of channel is shown in Figure 2.Figure 2
An example illustrating belief propagation algorithm for collaborative spectrum sensing.


## 3.2. Routing Scheme Based on Estimation of Path Duration

The estimation of path duration in cognitive maritime communications makes the routing efficient by exchanging geographic positions and beliefs of each ship with their neighboring ships. In this subsection, we explain how stable path is calculated by using beliefs obtained in the previous subsection. As this is cognitive ship-to-ship communication, the position of ships and channel condition are changing continuously with the movement of sea. All ships send messages to their neighboring ships about their positions and beliefs which are considered as additional entries in a beacon message. Therefore, each ship can calculate its distance from its immediate neighbors. We use theKalman filter to predict future positions of all the ships. We will discuss in Section 3.2.1 how we estimate the future values of position and velocity of ships by using theKalman filter algorithm.The estimation of path duration is helpful in selecting the path to transfer data packets from source to destination. An efficient routing protocol is required to estimate the path duration considering the challenges faced by marine environment. A few of existing routing protocols for terrestrial environment have been implemented in marine environment [14] and also some new routing protocols have been proposed for marine communications [1, 13]. We are concerned with the estimation of path duration to select a stable route for ship-to-ship communication as maritime link might be blocked by various propagation impairments. Therefore, we use both flood-based and geographical routing protocols to check their validity among challenges of maritime environment.To find a stable path between source and destination using AODV [8], aroute request (RREQ) is sent by the source node to all the neighbors in its communication range moving towards the destination. It is noteworthy that beliefs are updated as an additional entry among all the fields of RREQ. The RREQ passes through several nodes forming active links and then finally reaches the destination. Once the RREQ reaches the destination, the destination sends back aroute reply (RREP) to the source node. Hence, the stable path is calculated by computing the minimum link duration among all the links between source and destination for the common free channels, while GPSR [9] uses greedy forwarding to select next hop in making links with the source node. Three basic entities are used in applying greedy forwarding: the position of querying node, the position of all neighbors, and position of destination. The principle says that the source node selects that neighbor node which is the closest to the destination. Again, we mention here that in selecting the next node using GPSR all nodes send their beliefs as an extra entity in beacon message. Figure 3 explains the comprehensive algorithm by showing how source/relay selects the next hop nodes and beliefs of free channels jointly to reach the destination and then chooses the final route which maximizes the path duration among all the paths.Figure 3
A flowchart representing proposed algorithm.Two ships which are in the transmission range of each other having at least a common free channel calculate their link duration as follows:(11)LDij=Lij·min⁡bifH0,bjfH0,where Lij is the estimated time for which the direct link between two nodes within the transmission range of each other is active and is calculated in the same way as proposed by Liu et al. [18]: (12)Lij=R∓dijV,where R is the transmission range of ship i, dij is the distance between ship i and ship j, and V is the velocity of the ships. We will explain with examples the evaluation of Lij in Section 4. Hence, the path duration between source and destination is calculated as follows:(13)PDp=min⁡LD1p,LD2p,…,LDThp,where Th is the total number of hops between source and destination, p is index for path between source and destination, and p is from 1,…,P. Finally, a route p^ is selected which maximizes path duration among all the paths p:(14)p^=arg⁡maxp^∈p⁡PDp.


### 3.2.1.Kalman Filter Algorithm

As discussed in previous subsection, in order to make routing efficient by achieving a reasonable delay, we use aKalman filter in our proposed routing scheme to predict future positions of all ships. In this subsection, we briefly explain theKalman filter [19] algorithm. TheKalman filter has two vectors: state vector and measurement vector. The state vector consists of position Pt and velocity Vt of a ship; that is, ut=PtVt. The measurement vector is a measurement at time t. Two equations are used in this algorithm: a process equation and a measurement equation. The process equation predicts the future values of the ships at time t+1 and the measurement equation gives the observation value from the GPS. The process equation and measurement equation are defined by (15) and (16), respectively, as follows:(15)ut+1=Aut+εu,(16)zt=Hut+εz,where A and H are state transition and measurement matrices, respectively, εu is process noise, and εz is measurement noise. Both noises have a normal distribution with zero mean and a covariance matrix of Q and R, respectively.To measure the predicted and new values of moving ships, the algorithm is further divided into two steps: a prediction step and an update step. The prediction step predicts the state and covariance whereas the update step is a combination of predicted state and observation value. The predicted values are defined as follows:(17)u^t+1=Aut,Pt+1=APtAT+Q.And the new estimated values of each ship are defined as follows:(18)u^t+1∣t+1=u^t+1∣t+Kzt+1-Hu^t+1∣t,Pt+1∣t+1=Pt+1∣t-KR+HPt+1∣tHTKT,where K is theKalman gain calculated from(19)K=Pt+1tHTR+HPt+1tHT-1.Therefore, from the above equations, we can estimate the future values of position and velocity of ships by using theKalman filter algorithm.


## 3.2.1.Kalman Filter Algorithm

As discussed in previous subsection, in order to make routing efficient by achieving a reasonable delay, we use aKalman filter in our proposed routing scheme to predict future positions of all ships. In this subsection, we briefly explain theKalman filter [19] algorithm. TheKalman filter has two vectors: state vector and measurement vector. The state vector consists of position Pt and velocity Vt of a ship; that is, ut=PtVt. The measurement vector is a measurement at time t. Two equations are used in this algorithm: a process equation and a measurement equation. The process equation predicts the future values of the ships at time t+1 and the measurement equation gives the observation value from the GPS. The process equation and measurement equation are defined by (15) and (16), respectively, as follows:(15)ut+1=Aut+εu,(16)zt=Hut+εz,where A and H are state transition and measurement matrices, respectively, εu is process noise, and εz is measurement noise. Both noises have a normal distribution with zero mean and a covariance matrix of Q and R, respectively.To measure the predicted and new values of moving ships, the algorithm is further divided into two steps: a prediction step and an update step. The prediction step predicts the state and covariance whereas the update step is a combination of predicted state and observation value. The predicted values are defined as follows:(17)u^t+1=Aut,Pt+1=APtAT+Q.And the new estimated values of each ship are defined as follows:(18)u^t+1∣t+1=u^t+1∣t+Kzt+1-Hu^t+1∣t,Pt+1∣t+1=Pt+1∣t-KR+HPt+1∣tHTKT,where K is theKalman gain calculated from(19)K=Pt+1tHTR+HPt+1tHT-1.Therefore, from the above equations, we can estimate the future values of position and velocity of ships by using theKalman filter algorithm.


## 4. Performance Evaluation

We evaluate the performance of our proposed scheme in MATLAB. In this scheme, randomly placed ships are moving with various speeds up to the maximum speed of 50 km/h [1], each having a transmission range of 15 km. The variable I is varied from 5 to 20 and spectrum band is divided into M = 2 channels. The transmission power PT=25Watts and η can be any value between 0.5 and 1. The larger the value of η, the more the correlation between neighboring ships. We assume η = 0.9 which means the two states Hi and Hj are highly correlated hence yielding large probability for Hi=Hj. The path loss model described in (5) is used for simulation. Moderate sea state having wave height between 1.83 m and 2.29 m [15] is used primarily to evaluate the average path duration. Average path duration is defined as the average time for which a route is active between source and destination. Random values of wave height are generated for single iteration. Therefore, the value of SNR for each ship changes continuously. Our simulation results are the average of more than 50 runs. As we are testing our scheme for two routing protocols, therefore, for simplicity, we denote our proposed scheme as flood-based Cog-SANET (acronym of cognitive ship ad hoc network) when AODV is the routing protocol and geographical Cog-SANET when GPSR is used. We evaluate the expected path duration maximized routing (EPDM-R) [18] algorithm in marine environment to compare it with our proposed flood-based Cog-SANET scheme and named it as classic Cog-SANET for simulations. Classic Cog-SANET selects the route with maximum expected path duration among all attainable paths. This routing algorithm is similar to AODV in which freeway mobility model is used and behavior of PU is calculated using call-based model. This algorithm was initially proposed for CR-VANETs; we plot it in marine environment just for a reference.Figure4 shows the average path duration as a function of number of ships with probabilities of PU being idle as a parameter. The path duration increases with an increase in I, the number of ships. The reason for increase is the connectivity in the network due to increase in number of ships. Flood-based Cog-SANET performs better than geographical Cog-SANET when intermediate ships are moving freely in any direction in the network while source and destination are moving in the same direction. Flood-based Cog-SANET floods the RREQ to all the nodes in the transmission range of the querying node, therefore, making the links with each neighboring node it reaches the destination. The network has more paths to destination as compared to geographical Cog-SANET that makes the link only with the farthest node towards destination. Hence, flood-based Cog-SANET exhibits more stable paths as ships may remain in one’s transmission range for longer time, whereas geographical Cog-SANET makes shorter routes with short duration when intermediate ships are moving in opposite direction to the destination. Also, link stability depends on the distance between two moving nodes; as the separation increases (when nodes are moving in opposite direction from destination), the path duration decreases. An example is shown in Figure 5. Figure 4 also shows that as the probability of PU being idle decreases, the performance of path duration decreases. The reason for decrease is facing difficulty in finding common free channel with decrease in probabilities. Hence, by increasing the number of ships and the probability that PU is idle, we increase the stability of the paths in the network.Figure 4
Performance comparison between flood-based Cog-SANET and geographical Cog-SANET for average path duration as a function of number of ships with different probabilities of PU being idle as a parameter.Figure 5
An example illustrating that the farthest node when moving in opposite direction decreases duration of link.Figure6 shows the performance comparison of our flood-based Cog-SANET protocol with classic Cog-SANET. Classic Cog-SANET is also flood-based routing protocol proposed for cognitive VANETs; therefore, we do not compare it with geographical Cog-SANET. By considering collaborative spectrum sensing to select a free channel for communication and by predicting future positions of all the ships, our scheme outperforms classic Cog-SANET.Figure 6
Performance comparison between flood-based Cog-SANET and classic Cog-SANET for average path duration as a function of number of ships with different probabilities of PU being idle as a parameter.Figure7 shows performance of average path duration as a function of number of ships with different sea conditions as a parameter. We generate random values of wave height for calm (sea states 0–3), moderate (sea states 4-5), and high (sea states 6 and above) sea conditions as described by Pierson Jr. and Moskowitz [15] in their model and evaluate the performance of all three protocols for different sea states when ships are moving freely in any direction in the network. It can be seen from Figure 7 that higher sea states increase wave occlusion which occluded the link. The wave height h in (5) degrades the performance of whole network by rapidly increasing the path loss. An increase in h blocks the communication link between two ships which breaks the established route between source and destination. Therefore, the path duration decreases with an increase in wave height. We can also see from Figure 7 that flood-based Cog-SANET outperforms the other two routing protocols due to the same reason explained above. Evaluating this metric, we conclude that wave height h causes significant impact on the overall performance.Figure 7
Performance comparison between Cog-SANET and classic Cog-SANET for average path duration as a function of number of ships with sea states as parameter.Figure8 shows an exceptional case to test the performance of both flood-based and geographical routing protocols. A comparison is made between flood-based Cog-SANET and geographical Cog-SANET for average path duration when all intermediate ships are moving in the same direction to destination. Geographical Cog-SANET performs better than flood-based Cog-SANET because of the selection of an intermediate node which is the closest to the destination. Therefore, geographical Cog-SANET makes shorter routes with long link durations which in turn increase the path duration. GPSR always selects the further distanced node closer to the destination [9] while AODV not always makes paths with this farthest node. Broadly speaking, when all the ships are moving in the same direction, the chance for each node to stay in the communication range of its next node is increased (an example is shown in Figure 9). But this link may not be a stable link as it increases the chance of link breakage when any farthest node moves away from the transmission range of its previous node. Also, path duration increases with an increasing number of ships because it increases the chance for source/relay node to have more ships at the border line of one’s transmission range. This in turn increases the chance to form a link with the farthest node from source/relay node which increases the path duration.Figure 8
Performance comparison between flood-based Cog-SANET and geographical Cog-SANET for average path duration when all ships are moving with the same direction.Figure 9
An example illustrating the farthest node when moving in the same direction with source and destination.Figure10 shows the packet delivery ratio of the flood-based Cog-SANET, geographical Cog-SANET, and classic Cog-SANET for idle probability of PU, PH0 = 0.9. Packet delivery ratio is defined as the ratio of number of packets delivered to the destination to number generated by the source node. Figure 10 shows that the delivery ratio increases with an increase in the number of ships. We achieve 89% packet delivery for flood-based Cog-SANET when there are more ships because there are more links between source and destination as compared to geographical Cog-SANET. In geographical Cog-SANET, when source/relay node finds the farthest node towards destination but does not find common free channel, the packet will be dropped, while in flood-based Cog-SANET, there are other links available in the routing table of each node. Therefore, flood-based Cog-SANET outperforms the other two routing protocols. Furthermore, by considering the collaborative spectrum sensing and by predicting the future positions, both flood-based Cog-SANET and geographical Cog-SANET outperform the classic Cog-SANET.Figure 10
Performance comparison between flood-based Cog-SANET, geographical Cog-SANET, and classic Cog-SANET for packet delivery ratio.Figure11 shows the performance of end-to-end delay for flood-based Cog-SANET, geographical Cog-SANET, and classic Cog-SANET. End-to-end delay is defined as the difference between the start time and the end time of a packet going from source to destination. In cognitive marine environment, in addition to sea conditions and network connectivity, another factor that affects the performance of end-to-end delay is the selection of a common idle channel. As the number of ships increases, end-to-end delay decreases due to increase in connectivity. For less number of ships, the network is sparse; therefore, nodes spend more time in making connection with relay nodes to reach the destination. Both flood-based Cog-SANET and geographical Cog-SANET outperform classic Cog-SANET due to the same reasons explained above.Figure 11
Performance comparison between flood-based Cog-SANET, geographical Cog-SANET, and classic Cog-SANET for end-to-end delay.


## 5. Conclusion

In this paper, a novel scheme for cognitive maritime ad hoc networks is proposed. The combination of both channel selection and path selection makes this method unique. Channel selection is done by the cooperation of maritime users using BP algorithm and selection of path is achieved by two well-known routing protocols AODV and GPSR to test the validity of our protocol in both flood-based and geographical routing protocols. This is ship-to-ship cognitive routing technique in which a stable path is established between source and destination by combining beliefs of maritime users with their corresponding link durations for total number of hops between source and destination. Our results show that AODV outperforms GPSR in all cases except the one when all ships are moving with the same direction to the destination (an exceptional case). Moreover, our scheme shows better performance for average path duration when the sea state is calm and when ship density is high in the network. This work is valid only for maritime users above the sea surface. In future, we will extend this work for underwater communications.



---

*Source: 7635206-2016-04-14.xml*