LanePost: Lane-Based Optimal Routing Protocol for Delay-Tolerant Maritime Networks

Xiongfei Geng, Y ongcai Wang, Haoran Feng, Lu Zhang

1 China Waterborne Transport Research Institute, Beijing, China

2 School of Software and Microelectronics, Peking University, Beijing

3 Department of Computer Sciences, Renmin University of China, Beijing, China

4 National Engineering Research Center of Software Engineering, Peking University, Beijing, China

* The corresponding author, email: ycw@ruc.edu.cn

I. INTRODUCTION

People’s requirements for Internet accessing when they are on ships are growing rapidly.But current on-ship Internet accessing depends highly on the satellite links, which provide satellite-to-ship connections with 20 Mbps and provide user data rates up to 432 Kbps[1]. It is also too expensive to be frequently used by the general users. As a consequence, researchers and enterprisers are investigating to extend the high speed wireless networks from the land to the sea via multi-hop communication to provide maritime wireless mesh networks on the sea. Related projects including Triton[2] etc.,which exploited the recent advantages of IEEE 802.16m and WiMAX technologies for their long range (up to 50 Kilometers) communication feature to from ship-to-ship, ship-to-shore wireless links. But due to the low density and continuously mobility of the ships, frequent disconnections are expected and the network topologies vary continuously.

In such a low density, weak connectivity and highly dynamic network environment,data communication has to tolerate delays(when no other ships are nearby) and need to best utilize every temporal routing opportunity(when some ships come into communication range) to reduce the delivery delay and to improve the successful delivery rate. In such a circumstances, researchers investigated Delay Tolerant Network (DTN) configurations for the maritime environments[3][4], which transmit data following a “store and forward” approach, where data is stored at a ship as long as is necessary, until it is possible to be sent to the next hop. In such a way, each data holder(a node) is responsible to keep a data bundle(at the application layer) and to seek transmission opportunities for the bundle until it eventually reaches the destination. Such delay tolerant protocol can well support delay-tolerant applications such as email, video downloading with caching etc.

Routing protocol plays a critical role in such delay tolerant multi-hop networks. Previous works generally used replica-based routing methods, such as Epidemic Routing[5],RAPID [6], Probabilistic Routing [7] and SaW(Spray and Wait)[8]. Such protocols depend heavily on the message replication when two ships meet, which is the main mechanism to improve the message delivery rate in DTN routing in maritime networks. Network coding has also been exploited in the literature [9][10] for improving the flooding efficiency.

But a key problem in current research is the lack of optimization to the flooding-based DTN routing protocols, and therefore, the general unsatisfactory of message delivery delay in maritime networks. Previous works presented performance investigation to DTN routing in maritime environment. [4] compared the performances of regular routing protocols and delay tolerant network routing protocols and showed that the DTN routing achieved better end-to-end packet delivery ratio than the regular routing schemes in WiMax-based maritime networks. A later in [11] further evaluated the performances of several DTN routing protocols in maritime communications, which showed the generally large delivery delay and unsatisfied data delivery ratio in maritime environment. [3] presented MaritimeManet, a possible architecture of mobile Ad-hoc Networking at Sea, which is based on multiple directive beams for transmission. More DTN routing protocols will be introduced in detail in Section II.

How to optimize DTN routing in maritime networks remains a key challenge, which is addressed in this paper by a novel approach to exploit the shipping lane information. The key benefit of maritime DTN, which is different from the traditional urban DTNs is the general availability of the ship lane information,especially for ocean liners, i.e., the passenger ships. The passengers on the ocean liners are the major users of Internet oversea, and such kind of ships generally have very regular and predictable sealing lanes. The predictable shipping lane provides valuable information for DTN routing, which enables more efficient routing solution than the traditional DTN routing problem. Benefited by today’s widely usage of GPS and AIS (Automatic Identification System), the shipping lane informations can be collected to provide hints about when and where a ship will be within the communication ranges of the other ships, which provides valuable context for optimizing the DTN routing selections.

Therefore, in this paper, we propose opportunistic routing graph (ORG) to model the predicted lane intersecting opportunities,based on which, the DTN route optimization is carried out on the ORG via a proposed protocol, called LanePost. LanePost seeks the optimal forwarding path by dynamic programming to reduce the message delivery delay while guaranteeing the delivery ratio.For practice consideration, we discusses the cases when the shipping lane information is collected centrally using AIS (Automatic Identification System) data or distributively by inter-ship communications. The methods to address noises and inaccuracy of shipping lanes are also presented.

Note that in maritime DTN networks, we mainly consider the delay tolerable messages,such as email, QQ messages, Facebook messages. If large data need to be transferred, in DTN routing, the data is generally disassembled into slices and delivered as short packages and are assembled at the receiver using, for example, bit tolerant protocols.

We further presented extensive simulations via an open-source DTN network simulator.The evaluation results show that the proposed LanePost routing protocol can outperform existing DTN protocols dramatically, in terms of reducing the packet delivery delay while preserving the packet delivery ratio. The rest parts of this paper are organized as following. Related works are introduced in Section II. Problem model and opportunistic routing graph are presented in Section III. The Lane-Post routing protocol is presented in Section IV. Performance evaluations are introduced in Section V. Conclusions are drawn in Section VI with discussions of future work.

II. RELATED WORKS

The study of routing protocols in maritime mesh networks have attracted great research attentions.

2.1 Maritime mesh networks

To overcome the long range ship-to-ship and ship-shore communication, radios such as WiMax, MF (medium frequency), HF (high frequency), VHF (very high frequency), IEEE 802.16m, and LTE were exploited as major long-range communication techniques in maritime networks. A comparison of these radio techniques was discussed in [12], which proposed the idea of nautical ad-hoc network for maritime communications. In an early TRITON project [13], [14], the authors presented the development of IEEE 802.16m-based lowcost mesh network in narrow sea areas in Singapore. They reported the link qualities, network connectivities and ship density impacts based on the real AIS data. The signal strength signatures affected by the sea surface reflection and their effects to routing were studied in [15] in IEEE 802.16m-based maritime networks.

For WiMax-based maritime mesh networks,a soft handover solution [16] was developed by Hoang et.al, to enable mobile WiMax multi-hops mesh networks. The time slot allocation problem for WiMax based maritime network was studied in [17], which proposed a distributed MAC protocol for communication collision avoidance. To further improve the radio access of maritime networks to find dedicated spectrums in current congested bandwidth allocations, cognitive maritime wireless mesh networks with cognition-enhanced MAC protocol and switching antenna were proposed in [18], which showed that better network performances could be achieved by higher detection probability and a longer channel sensing interval.

2.2 Routing protocols in maritime mesh networks

Routing protocol plays a critical role in maritime mesh networks. When ships’ lanes are within a narrow channel, which restricts the maritime network to have good connectivity,the performances of regular routing protocols including Optimized Link State Routing(OLSR) [19], Ad Hoc On Demand Distance Vector (AODV) Routing [20] and Ad Hoc On Demand Multipath Distance Vector (AOMDV)[21] were compared in [22]. These routing protocols showed reasonable performances only when ships are in good density, which requires the ship-to-shore and ship-to-ship radio ranges can be larger than 35Km and 20Km respectively.

To deal with the more general cases of low density and frequent disconnection, the DTN routing protocols [23] have attracted great research attentions in the study of maritime networks. The DTN network routing protocols can be divided into three categories:

1) Replica-based (flooding) protocols:including Epidemic Routing[5], RAPID [6],Probabilistic Routing [7] and SaW (Spray and Wait)[8], etc. The common feature of these protocols is to generate multiple copies of message via message relay to increase the probability of message delivery to the destination. The difference among these protocols is the different method to control the message duplication. Epidemic routing [5] simply exploits the message flooding. In RAPID[6], a utility function is defined; only the packets that can increase the utility function will be replicated. In SaW[8], two different upper bounds on the number of copies were set for Spray phase and Wait phase respectively. In Probabilistic routing[7], the message is forwarded to another node only if the forwarding node have enough high probability to meet other nodes.

2) Knowledge based routing protocols:including geographical routing[24], gradient routing based on link metrics [25]. These routing protocols require some knowledge about the network topology information before hand to transfer data in the best path without blindly replicating.

3)Coding based routing protocols: which exploited network coding to improve delivery rate and security. Examples include the estimation based Erasure Coding (EBEC)[9]and Hybrid Erasure coding (HEC)[10]. These methods not only utilize the robustness of the erasure coding, but also benefited by the delivery rate of the replication techniques. For more introduction of these routing algorithms,please refer to the survey [23].

In maritime DTN networks, ships have even less opportunities to meet and messages have longer transmission delay. Current routing protocols for DTNs generally rely on redundant packet flooding to seek higher probability of packet delivery, without special consideration to ship lane characteristics. How to design an optimal routing protocol with the minimum routing delay in maritime networks is still a challenging problem.

III. PROBLEM MODEL

3.1 Lane model

We consider N ships are sailing on a two-dimensional ocean surface following their designated lanes, in which the ocean surface is considered flat without affecting the routing protocol design. The shipping lanes are modeled as piece-wise linear curves on the earth water surface, which indicate the sailing paths of the ships over the sea ( see Definition2). The lane information of the ships are generally defined by the strategic trajectories of physical constraints (coasts, winds, marine currents, depth,reefs, ice), by the political borders, and by the sailing plans of the ships. Main shipping lanes are those supporting the most important commercial shipping flows servicing the major markets. Secondary shipping lanes are mostly connectors between smaller markets [26].Since current ships are widely equipped with GPS, the shipping lane information are widely monitored by global or local area ship tracking systems [27][28].

Fig.1 Lane-based multi-hop routing in Maritime DTN networks

We consider each ship is equipped with a GPS, so it knows its own location. We denote the location of ship i at time t by xi,t.Each ship is equipped with a short-range,wideband wireless communication module for internship or ship-to-shore multi-hop data communication, such by WiFi or WiMax. The communication radius, i.e, the maximum communication range of short-range modules is denoted by r, which generally from 1Km to 10 Km. Ships are also equipped with long-range communication modules, such as Medium Frequency (MF)/High Frequency (HF)/Very High Frequency (VHF) modules [29] with communication range larger than 50 Km. The communication range of the long-range radio is denoted by R. Note that the long-range radio can only be used to transmit low data rate packets. Only the short-range wideband radio can be used for internet applications.

3.2 Communication model

The multi-hop data communication problem is that: each ship generates data randomly, which need to be delivered to the base stations on the shore (we assume the base stations are densely distributed on the shore, so that data can be delivered to based station only if the ships reach the shore). The ship reaching the shore delivers all its carried data to the base stations.The inter-ship data communication is multihop and delay-tolerant.

The conditions for inter-ship or ship-toshore communication are that the two ships are within the communication range r or the ship has distance less than r to the shore. The multi-hop path for data delivery from a source location s to a destination location d is therefore modeled by an opportunistic routing path(ORP):

Definition 1 (Opportunistic Routing Path):Each path Pistarting from s, ending at d is composed by a set of pairwise, meetable nodes(ships or shore), i.e., {vi,1, vi,2, · · · , vi,k}, where vi,1=s and vi,k=d. The meeting time between vi,j−1and vi,jmust be earlier than the meeting time between vi,jand vi,j+1, to guarantee the message isfirstly transmitted from vi,j−1to vi,jand then from vi,jto vi,j+1.

For a given source s and a destination d,there maybe many opportunistic routing paths from s to d. The problem of multi-hop routing in the dynamic maritime networks is to determine these opportunistic routing paths and then to conduct optimization to select the optimal path has better performances, i.e, shorter delay and higher delivery ratio to route data.

3.3 Lane-based routing in DTNs

The shipping lane information will provide vital knowledge for determining the opportunistic routing paths, because when and where will two ships meet can be told by the lane information of the ships.

Definition 2 (Piecewise Linear Shipping Lane): A ship’s lane information is approximated by a piecewise linear curve, denoted by Li= {{t1, x1}, {t2, x2}, · · · , {tT, xT}}, where xjis the location of the ship at time tj; {tj, xj}and {tj+1, xj+1} are the starting point and ending point of the line segment j.

If the lane information of the N ships are available, for each given s and d the opportunistic routing paths can be determined and the optimal routing path can be selected via evaluating the potential delays and delivery ratio. An simple example is shown in Fig.1 to illustrate the basic idea of lane-based routing.In thefigure, four ships are sailing following their lanes. The black solid curves indicate the lanes of the ships. The dashed red lines show the optimal routing path for the ship C to transmit its data to the Internet. From the information of the lanes, we can see that ship A and B will meet (be within communication range) at point x before A reaching the shore,so that at the instance when B and D are in the communication range of C, C will prefer to transmit data to B to form a multi-hop delay tolerant path from C → B → A → Shore. The intuition motivates us to explore the

lane-based optimal routing protocol for maritime networks.

IV. LANEPOST PROTOCOL

We investigate how the lane information can help to optimize the routing protocol design.

4.1 Lane graph

At first, we consider the ideal case when the lane information of all the ships are perfectly available at a server, i.e, we have the perfect shipping plans and routing information of all the ships. At this stage, we assume the ship information is available, and we will discuss how the shipping lane information can be obtained in the next section. We denote the shipping lane information of the N ships by {L1,Note that Li= {{t1, x1}, {t2, x2},··· , {tT, xT}} is the piecewise lane of the ship i, indicating the locations of the ship overtime.To utilize the lane information for the routing protocol design, we propose lane graph,which is constructed to indicate the meeting(i.e., be within the communication radius of each other on the sea surfaces) possibilities and the meeting times of the ships. The problem of lane graph construction is to determine the rendezvous time and location of any two ships when their motion models are given by the piecewise linear functions. Let xi,tand xj,tbe the locations of ship i and ship j at time t,then the condition for these two ship meeting at time t is:

Definition 3 (Lane Graph): Lane graph is defined as a weighted graph G = (V, E, W )where the vertex set V includes all the ships and a node s indicating the shore. An undirected edge (i, j) exists if the node i and the node j can meet at some time t. The weight wi,j of edge (i, j) is a vector composed bywhich indicate the meeting times of the two nodes; m is the total number of meeting times of the two nodes during their overall trips.

The pseudo codes of lane graph construction are provided in Algorithm 1, which is actually a brute-force search over all the shipping lanes to find the meeting opportunities and the meeting times of the ships. Its computation complexity is O(|T||V|2).

An example of lane graph construction is shown in Fig.2. Fig.2(a) shows the lane information of six ships. According to spatial and temporal constrains, some ships will meet at different times and locations. Based on the ship meeting information, Fig.2(b) shows the constructed lane graph for the six ships. In this example, there are eight meeting events,which map to eight edges. Fig.2 (c) shows the ordered meeting times of these meeting events.

The lane graph is the foundation for lanebased routing optimization, since it provides important information about when two nodes can meet in the mobile, dynamic maritime networks and embeds these information into the edges, which can be easily searched over the lane graph. We can sort these meeting events by by time, i.e., weights of edges to determine the occurrence sequence of the meeting events.

4.2 Opportunistic routing graph

As given in Definition 1, a critical problem for optimizing the routing selections from s to d is to determine the opportunistic routing paths from s to d. In the lane graph, because each edge indicates the meeting opportunities of the connected nodes, we can infer the opportunistic routing paths from given s and d by searching the lane graph. All the paths from s to d will form a new graph, called opportunistic routing graph (ORG).

?

Fig.2 Example of the “lane graph” and the “opportunistic routing graph” construction based on the lane information of the ships

?

Definition 4 (Opportunistic Routing Graph): The opportunistic routing graph from a source s to a destination d is a directed,weighted graph Gs,d= {Pi}, containing a set of opportunistic routing paths from s to d.Each path Piis composed by a set of pairwise,meetable nodes, starting from s and ending at d, i.e., {vi,1, vi,2, · · · , vi,k}, where vi,1=s and vi,k=d. The meeting time between vi,j−1and vi,jmust be earlier than the meeting time between vi,jand vi,j+1, to guarantee the message isfirstly transmitted from vi,j−1to vi,jand then from vi,jto vi,j+1. Each two adjacent nodes are connected by a directed edge from vi,jto vi,j+1.

Given a lane graph G, a source node s and a destination node d, the construction of Gs,dbased on G has two steps.

1. Thefirst step is to conduct Breadth-First-Search over G to construct a BFS tree rooted at s and has d as the leaf nodes. Note that, in this step only the meeting events after current time will be exploited because the previous events can no longer help to transmit data for s.

2. The second step is to select all the paths from s to d on the BFS tree to form the opportunistic routing graph Gs,dfor current time message. Algorithm 2 describes the two steps for extracting the opportunistic routing graph Gs,dfrom Lane-graph G. The complexity of the algorithm is O(|E|+|V|) where E and V are the edge set and vertex set of G.

4.3 Lanepost delay optimal routing

Once the opportunistic routing graphs for given s and d are constructed, all the opportunistic routing paths provided by the shipping lanes are known. In each path, the message arriving time at the destination is indicated by the meeting time of the last node in the path with the destination d. The message transmis-sion delay is defined as the time interval from the time when the message was generated from s to the time when the message arrives at d. Therefore, to minimize the message transmission delay from s to d, LanePost selects the opportunistic routing path whose last meeting time to the destination d is the earliest. The overall LanePost routing protocol is summarized in Algorithm 3:

Theorem 1 (Optimality): For any given s and target d, LanePost provides the optimal routing path in minimizing the message transmission delay from s to d.

Proof: Because the Lane-graph has considered all the meeting opportunities of ships for message transition, the opportunistic routing graph Gs,dconstructed from the Lane- graph has included all the possible delay tolerant paths from s to d. So that the path with the shortest delay is the overall optimal path for delay minimization.

V. IMPLEMENTATION OF LANEPOST

From the analysis, we see LanePost provides the optimal routing path in maritime network in the ideal case. However in implementation,there are practical issues need to be considered.

5.1 How to collect the lane information?

The first problem is that how can we collect the lane information of the ships. There are actually three ways to do this.

1) To provide internet services to the onship users, it is reasonable to consider only the large vessels that can take passengers. Such kind vessels are generally equipped with satellite, AIS systems and their shipping lanes are regular and predefined. Their lane information can be easily reported by satellite or AIS links to the server.

2) If smaller ships without satellite or AIS system are considered, still, long-range communication radio, such as MF/HF/VHF radios are equipped on these ships. So when such a small ship is in the communication range R of a large vessel that has the satellite or AIS links, it can report its lane information to the large vessel via the long-range communication radio and the large vessel will report the lane information to the server.

?

3) Ships generally have predefined shipping routes and work periodically, so that the historical lane information of the ships can also be used to infer its predicted lane.

Via these methods, the lane information of the ships can be collected, which can then be approximated piecewise linear curves to construct lane graph and be used for LanePost.

5.2 Deal inaccuracy of the predicted lanes

In the previous discussions, we assume the shipping lanes are perfectly known after being collected, but in practice, for the dynamic and hazardous environments over the sea, the shipping lane information can never be perfectly predicted. In the optimal LanePost, only the optimal routing path from s to d is selected to route data from s to d. Although its delay is the optimal, it is not reliable for data delivery when the lane information is not accurate. To tackle this problem, we exploit two schemes to improve the reliability of LanePost against the lane noises:

1) Multi-path routing: instead of selecting one routing path, we select the top-K, i.e.,multiple routing paths to tolerate the noises of the lanes. This can be simply carried out in Algorithm3 by selecting the top-K minimum delay paths to route data from s to d.

2) Enhance meeting condition to tolerate lane noises: The second strategy is to make the meeting condition more restrict. In ideal case, two ships can meet, i.e., are supposed to communicate to each other only if they are in the communication radius r at some time.By reducing r, this meeting condition will become more restrict. For example if we reduce r to r′＜r, it will restrict that only when the predicted positions of two ships are within r′,can they be considered have the opportunity to meet.

Let’s further see how the enhancement of meeting condition can help to tolerate lane noises. Considering two ships, a and b, if their predicted distance at time t are less than r′,then they are predicted to meet at time t. In practice, according to lane noises, if the deviation of these ships to their predicted locations are daand dbrespectively, then it is easy to prove that:

Proposition 1 (communication condition with lane noises): If two ships are predicted to be within distance r′; if the lane noises cause their real positions deviate to the predicted positions by da and db respectively, then these two ships can communicate against the lane noise in practice only if:

Proof: If the predicted distance is d′＜r′, the real distance d′ must be less than d′+da+db,which is less than r′+da+db. Since da+db＜r−r′,then d′＜r. An example of the proof is shown in Fig.3.

Therefore by introducing the restricted communication radius in LanePost protocol,the noise of lane information can be tolerated.

VI. SIMULATION RESULTS

With above practical considerations, we developed three versions of LanePost protocol:

Fig.3 restrict the meeting condition to tolerate the noises of shipping lanes

1) Ideal LanePost (iLanePost), which routes data to the delay-optimal single routing path;

2) Multi-path LanePost (mLanePost), which routes data to the top-K optimal routing paths;

3) Multi-path LanePost with consideration of restricted meeting conditions (mrLanePost)to tolerate the noises of shipping lanes.

We evaluated the performances of these protocols using the ONE simulator, i.e., Opportunistic Network Environment simulator[30]. The ONE is a simulation environment that is capable of simulating node movements using different movement models; routing messages between nodes with various DTN routing algorithms and sender and receiver types. It is based on Java and provides a graphical user interface to visualize both mobility and message passing in real time. By using the ONE simulator, we compared the multi-hop transmission delay, communication costs and the data delivery performances of the proposed protocols with the performances of Epidemic routing [5] and Spray&Wait [8]protocols in DTN networks.

6.1 Simulation by manhattan model

To generate the shipping lanes, we used the BonnMotion [31], a mobility scenario generation and analysis tool to generate the mobility scenarios of the ships. BonnMotion is a Java software which creates and analyzes mobility scenarios and is most commonly used as a tool for the investigation of mobile ad hoc network characteristics. The generated motion scenarios of BonnMotion can be directed imported into the One simulator. BonnMotion supports more than ten types of mobility models. In this paper, to simulate the mobility of ships, we generated the shipping lanes using the Manhattan Grid model, in which the nodes (ships)moves only on predefined paths. The Manhattan Grid model generates grid type routing paths for the ships. It has two augments u and v, which set the number of blocks between the paths. We set the right and down areas of the simulation area as the shore. Only when the ships are within the communication radius from the shore it can upload and download data from the access points on the shore. Each ship is randomly deployed on a path in the generated Manhattan motion map and choses a random moving direction from “east, west,south, and north”.

In simulation, without losing of the generality, we only evaluate the cases when the ships transmit data towards the shore. Each ship generated a random volume of data uniformly distributed from 1M to 10M and the goal of routing protocol is to delivery the data generated by all ships to the shore. The settings of different simulations are listed in Table I.

6.2 Simulation results

Based on above simulation settings, the data delivery rate, the communication costs and the multi-hop data transmission delays of the proposed routing protocols are compared together with Epidemic routing [5] and Spray&Wait [8]protocols.

1) Performances without Lane Noises: At first, we evaluated the cases when the lane information of the ships are exact. In this case,since the meeting events can be accurately predicted by the lane information, it is not necessary to conduct multi-path lanePost, nor restricting the meeting conditions. Therefore,in this case, only the performances of iLane-Post are compared with that of the Epidemic routing and Spray&Wait.

Fig.4 shows the evaluated performances of iLanePost, Epidemic routing, and Spray&Wait,from which, we can see that iLanePost achieved the packet delivery ratio as good as Epidemic routing; the number of transmitted packets in LanePost is much lower than that of Epidemic routing and Spray&Wait; the average delivery delay in iLanePost is also much shorter than that of Epidemic routing and Spray&Wait. The results indicate that, via LanePost, we can achieve the optimal data delivery ratio as good as Epidemic routing but paying very low transmission and delay costs.

2) Performances with Lane Noises: Secondly, we consider the cases when the shipping lane information is not exact. To simulate the lane errors, at each time, random noises(randomly generated from (0 − 1)Km are added to each ship’s x, y coordinates to simulate its position deviation from its predicted lane. In such a setting, the performances of the proposed protocols are shown in Fig.5. It can be seen that rmLanePost, mLanePost and iLanePost achieved good packet delivery ratio which is only a little worse than Epidemic routing, but the communication cost and the packet delivery delay are much lower. The results indicate that even noisy lane information can great help routing protocol optimization in DTN.

Table I Parameter settings in simulation

6.3 Evaluation using real dataset

In addition to evaluate LanePost by ship lanes generated by simulations, we also used real ship lanes collected from AIS dataset to evaluate the effectiveness of propose algorithms.We used AIS dataset provided by BoLooMo International Group Ltd, http://www.boloomo.com. BoLooMo runs the second large ship management system in China. It collects more than ten thousands ship location information in every minute. Each message of the ship location information includes 1) the ship ID,2) a times temp; 3) longitude; 4) latitude of the ship at that time instance. We used Matlab to convert the AIS messages into traces information of ships. We treat the trace of each ship as its lane information in the period. For effectiveness of evaluation, we selected 100 ships lanes in ten days in the area of Chinese Bohai gulf. The lanes of ten ships within one day was shown in Fig.6.

Fig.4 Packet delivery probability and number of packet transmissions for different protocols in the scenarios of different number of ships when the lane information is accurate

Fig.5 Packet delivery probability and number of packet transmissions for different protocols in the scenarios of different number of ships when the lane information is noisy

Fig.6 Example traces of 10 ships in one day in the chose AIS dataset

Then the lanes of ships were imported by BonnMotion software to build the mobility models of the ships. Then the mobility models were used in ONE simulator to construct the lane graph of ships and the opportunistic routing graph for LanePost. Then, in evaluation of the LanePost routing protocol, the ship with the largest distance to the shore was selected as the source node and the shore is selected as the destination. The message delivery performances, including the message delivery ratio, the message transmission cost, and the message delivery delay were evaluated for the setting of 100 ships in the selected area.

The performance evaluation results were shown in Fig.7. We can see, similar to the simulation results, LanePost has obviously shorter message delivery delay than Epidemic routing and Spray&Wait. It also need much less transmission cost than Epidemic routing and Spray&Wait, while it also provides high message delivery ratio as good as Epidemic routing.

VII. CONCLUSION

This paper investigated how to utilize lane information of ships to optimize the routing protocol design in delay-tolerant, multi-hop,maritime networks. We proposed LaneGraph to model the lane information over the sea,and opportunistic routing graph (ORG) to model the rendezvous opportunities of the ships, based on which, we present a delay optimal routing protocol, i.e., LanePost. Lane-Post conducts dynamic programing to utilize the predicted meeting probabilities of the ships to select the optimal delay-tolerant path to route data. The methods to collect the lane information and the methods to deal with the noises of lane information are also presented.Simulations using ONE simulator and AIS data set were conducted. The results showed that the proposed LanePost protocol had advantage in transmission cost and transmission delay reduction while providing good packet delivery ratio.

ACKNOWLEDGMENT

This work was supported in part by National Natural Science Foundation of China Grant 61672524; the Fundamental Research Funds for the Central University, and the Research Funds of Renmin University of China,2015030273; and National Key Technology Support Program 2014BAK12B06.

Fig.7 Performance evaluation results using AIS dataset

[1] Kenneth Y. Jo.Satellite Communications Network Design and Analysis. Artech House, 2011.

[2] Yu Ge, Peng-Yong Kong, Chen-Khong Tham,and J.S. Pathmasun- tharam. Connectivity and route analysis for a maritime communication network. In2007 6th International Conference on Information, Communications Signal Processing, pages 1–5, 2007.

[3] J.H. Laarhuis. MaritimeManet: mobile ad-hoc networking at sea. InWaterside Security Conference (WSS), 2010 International, pages 1–6, 2010.

[4] Hao-Min Lin, Yu Ge, Ai-Chun Pang, and J.S.Pathmasuntharam. Performance study on delay tolerant networks in maritime communication environments. InOCEANS 2010 IEEE - Sydney,pages 1–6, 2010.

[5] Ram Ramanathan, Richard Hansen, Prithwish Basu, Regina Rosales- Hain, and Rajesh Krishnan. Prioritized epidemic routing for opportunistic networks. InProceedings of the 1st International MobiSys Workshop on Mobile Opportunistic Networking, MobiOpp ’07, pages 62–66,New York, NY, USA, 2007. ACM.

[6] Aruna Balasubramanian, Brian Levine, and Arun Venkataramani. DTN routing as a resource allocation problem. InProceedings of the 2007 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, SIGCOMM ’07, pages 373–384, New York, NY, USA, 2007. ACM.

[7] Anders Lindgren, Avri Doria, and Olov Schele´n.Probabilistic routing in intermittently connected networks.SIGMOBILE Mob. Comput. Commun.Rev., 7(3):19–20, July 2003.

[8] Thrasyvoulos Spyropoulos, K. Psounis, and C.S.Raghavendra. Spray and focus: Efficient mo-bility-assisted routing for heterogeneous and correlated mobility. InFifth Annual IEEE International Conference on Pervasive Computing and Communications Workshops, 2007. PerCom Workshops ’07, pages 79–85, 2007.

[9] Yong Liao, Kun Tan, Zhensheng Zhang, and Lixin Gao. Estimation based erasure-coding routing in delay tolerant networks. IWCMC ’06, pages 557–562, New York, NY, USA, 2006. ACM.

[10] Ling-Jyh Chen, Chen-Hung Yu, Tony Sun, Yung-Chih Chen, and Haohua Chu. A hybrid routing approach for opportunistic networks. InProceedings of the 2006 SIGCOMM Workshop on Challenged Networks, CHANTS ’06, pages 213–220, New York, NY, USA, 2006. ACM.

[11] L. Lambrinos, C. Djouvas, and C. Chrysostomou.Applying delay tolerant networking routing algorithms in maritime communications. InWorld of Wireless, Mobile and Multimedia Networks(WoWMoM), 2013 IEEE 14th International Symposium and Workshops on a, pages 1–6, 2013.

[12] YoungBum Kim, JongHun Kim, YuPeng Wang,KyungHi Chang, Jong Won Park, and Yong-Kon Lim. Application scenarios of nautical adhoc network for maritime communications. InOCEANS 2009, MTS/IEEE Biloxi - Marine Technology for Our Future: Global and Local Challenges, pages 1–4, 2009.

[13] J.S. Pathmasuntharam, J. Jurianto, Peng-Yong Kong, Yu Ge, Mingtou Zhou, and R. Miura. High speed maritime ship-to-Ship/Shore mesh networks. InTelecommunications, 2007. ITST ’07.7th International Conference on ITS, pages 1–6,2007.

[14] J.S. Pathmasuntharam, Peng-Yong Kong, Ming-Tuo Zhou, Yu Ge, Haiguang Wang, Chee-Wei Ang, Wen Su, and H. Harada. TRITON: high speed maritime mesh networks. InIEEE 19th International Symposium on Personal, Indoor and Mobile Radio Communications, 2008. PIMRC 2008, pages 1–5, 2008.

[15] Chee-Wei Ang and Su Wen. Signal strength sensitivity and its effects on routing in maritime wireless networks. In33rd IEEE Conference on Local Computer Networks, 2008. LCN 2008, pages 192–199, 2008.

[16] Vinh Dien Hoang, Maode Ma, R. Miura, and M.Fujise. A novel way for handover in maritime WiMAX mesh network. InTelecommunications,2007. ITST ’07. 7th International Conference on ITS, pages 1–4, 2007.

[17] Peng-Yong Kong, Haiguang Wang, Yu Ge,Chee-Wei Ang, J.S. Path- masuntharam, Wen Su, Ming-Tuo Zhou, and H. Harada. Distributed adaptive time slot allocation for WiMAX based maritime wireless mesh networks. InIEEE Wireless Communications and Networking Conference, 2009. WCNC 2009, pages 1–6, 2009.

[18] Ming-Tuo Zhou and Hiroshi Harada. Cognitive maritime wireless mesh/ad hoc networks.Journal of Network and Computer Applications,35(2):518–526, March 2012.

[19] P. Jacquet, P. Muhlethaler, T. Clausen, A. Laouiti,A. Qayyum, and L. Viennot. Optimized link state routing protocol for ad hoc networks. InMulti Topic Conference, 2001. IEEE INMIC 2001. Technology for the 21st Century. Proceedings. IEEE International, pages 62–68, 2001.

[20] C.E. Perkins and E.M. Royer. Ad-hoc on-demand distance vector routing. InSecond IEEE Workshop on Mobile Computing Systems and Applications, 1999. Proceedings. WMCSA ’99, pages 90–100, 1999.

[21] M.K. Marina and S.R. Das. On-demand multipath distance vector routing in ad hoc networks. InNinth International Conference on Network Protocols, 2001, pages 14–23, 2001.

[22] Peng-Yong Kong, Haiguang Wang, Yu Ge, Chee-Wei Ang, Su Wen, J.S. Pathmasuntharam, Ming-Tuo Zhou, and Hoang Vinh Dien. A performance comparison of routing protocols for maritime wireless mesh networks. InIEEE Wireless Communications and Networking Conference, 2008.WCNC 2008, pages 2170–2175, 2008.

[23] S. Ali, J. Qadir, and A. Baig. Routing protocols in delay tolerant networks - a survey. In2010 6th International Conference on Emerging Technologies (ICET), pages 70–75, 2010.

[24] Pei-Chun Cheng, Kevin C. Lee, Mario Gerla,and Jrme Hrri. GeoDTN+Nav: Geographic DTN Routing with Navigator Prediction for Urban Vehicular Environments.Mobile Networks and Applications, 15(1):61–82, June 2009.

[25] E.P.C. Jones, L. Li, J.K. Schmidtke, and P.A.S.Ward. Practical Routing in Delay-Tolerant Networks.IEEE Transactions on Mobile Computing,6(8):943–959, August 2007.

[26] Sea lane, February 2014. Page Version ID:593873672.

[27] http://www.chinaports.com/shiptracker/. Chinaport ship tracker.

[28] https://www.marinetraffic.com. Marinetraffic.

[29] Medium frequency, February 2014. Page Version ID: 592874332.

[30] Ari Kera¨nen, Jo¨rg Ott, and Teemu Ka¨rkka¨inen. The ONE simulator for DTN protocol evaluation. Simutools ’09, pages 55:1–55:10, ICST,Brussels, Belgium, Belgium, 2009.

[31] Raphael Ernst Nils Aschenbruck. BonnMotion: a mobility scenario generation and analysis tool.page 51, 2010.