CN110752987B - Community-based ship network routing method - Google Patents

Abstract

The invention discloses a community-based ship network routing method, and specifically relates to the technical field of data transmission of marine ship ad hoc networks. The method calculates the social relationship between ships according to the historical navigation information of the ships and constructs the ship social network based on this method, and guides the next hop selection of the route according to the encounter probability between the ships reflected in the ship social network information. The routing method mainly includes the following steps: firstly, the ship uploads historical and real-time navigation information to the ship network, and generates a ship social network composed of social familiarity between ships. Second, the ship social network is divided into communities, and the communication intermediary ability of each ship between different communities is calculated. Finally, the ship will choose the same community as the target ship or a ship with stronger communication ability to the target community as the next hop. This routing protocol greatly reduces the transmission cost on the basis of ensuring the transmission success rate and transmission delay, and is very suitable for the ship Organizational network.

Description

Community-based approach to ship network routing

technical field

The invention relates to the technical field of data transmission of marine ship ad hoc networks, in particular to a community-based ship network routing method.

Background technique

The wireless self-organizing network communication technology of marine ships is the core technology and important guarantee for the development of marine Internet of Things, smart marine engineering, marine fishery construction, and international marine cargo transportation. At present, the wireless communication methods of offshore ships mainly include near-shore cellular network wireless communication, maritime communication satellite, IF/HF/VHF radio communication, single sideband wireless communication, fishing walkie-talkie, etc. Ship wireless ad hoc network, as a new type of marine ship wireless communication technology, has the advantages of low cost, high efficiency, high reliability, high flexibility, etc. technology research and system development.

The characteristics and limitations of the existing wireless communication methods for marine ships mainly focus on the coverage, deployment cost, communication cost, communication speed and bandwidth, and communication stability. First of all, ships such as fishing boats operating offshore and cargo ships entering the port can use mobile phones to access the near-shore cellular base station for communication, but the coverage of shore-based cellular wireless communication can only reach a distance of about 10 nautical miles or 15 kilometers offshore. Support real-time communication of far-sea fishing vessels or ocean-going freighters. Second, the communication method based on maritime communication satellite or mobile communication satellite has the advantages of wide coverage and strong real-time performance, but the communication cost is high and the communication bandwidth is small, so it is more commonly used for communication in emergency situations. Third, the medium and high frequency radio communication mode, its communication distance varies from tens of nautical miles to hundreds of nautical miles, but its communication quality is poor, mainly one-way communication, and needs to be equipped with special radio transceivers, relying on professional operators It is generally used in the marine traffic management system of large-tonnage ocean-going ships and freighters, such as automatic ship identification systems. Fourth, single-sideband wireless communication improves the anti-interference ability and communication quality compared with medium and high frequency radio communication, but the communication equipment is more complicated, the blind area is larger, and both parties of voice communication cannot speak at the same time. Finally, the fishing walkie-talkie is a kind of communication method with low cost, flexible and convenient equipment and use, and limited communication distance. It is mainly used for local instant communication in fishing boat formations. In summary, the existing wireless communication methods for marine ships cannot meet the increasing communication needs of different types of marine ships, especially in terms of low cost, high bandwidth, immediacy, stability, and flexibility of communication. There is a huge gap. Ship wireless ad hoc network is a kind of example of wireless mobile ad hoc network, similar to vehicle ad hoc network, mobile sensor network and so on. The main research content of ship wireless ad hoc network technology is based on the limited distance wireless communication capability between mobile nodes, self-organizing efficient and reliable multi-hop data transmission in a distributed computing manner, and realizing node positioning of the entire network. /Data routing/Anomaly detection/Environment monitoring and other network application targets. Ship wireless ad hoc network technology has the advantages of low deployment and communication costs, high communication efficiency, wide coverage, and flexible application.

The current research on ship self-organizing network routing algorithm is basically blank, and the related research is not based on real ship trajectory data. Most of them use simulators to simulate the motion of ships to achieve simple routing simulation. There is no research to analyze the characteristics of the ship network, and there is no routing algorithm for the ship's self-organizing network.

SUMMARY OF THE INVENTION

The purpose of the present invention is to solve the above shortcomings, and propose a method based on in-depth analysis of the ship's trajectory data, mining the inherent social connections between ships, building a ship's social network, dividing the ship's social community, and narrowing the transmission range of data packets. A community-based approach to routing networks in ships.

The present invention specifically adopts following technical scheme:

A community-based approach to ship network routing, including the following steps:

Step 1: The ship uploads the navigation information and the encounter information with other ships in a distributed manner through the communication at the time of encounter;

Step 2: The ship network platform calculates the social familiarity F(a, b) between ships according to the navigation information uploaded by the ship and the encounter information between ships. The specific calculation formula is shown in formula (1):

表示两条船相遇时的状态所对应的权重，当船a与船b相遇时都处在捕鱼状态时，则此相遇状态对a和b两条船之间的社交关系增益为α，当船a与船b相遇时都在航行则社交增益为β，如果两者相遇时状态不一样时，社交增益为γ，T表示两条船一段时间内总的相遇次数，τ表示某一相遇的持续时间；in,

Represents the weight corresponding to the state of the two boats when they meet. When boat a and boat b are both in fishing state when they meet, then this encounter state has a social relationship gain between the two boats a and b. When When ship a and ship b meet, they are both sailing, and the social gain is β. If the state of the two ships is different when they meet, the social gain is γ. T represents the total number of encounters between the two ships in a period of time, and τ represents a certain encounter. duration;

Step 3: Take the ship as a node, and use the social familiarity F(a, b) between ships as the weight of the edge to build a ship social network;

Step 4: Use the community detection algorithm Louvain algorithm to divide the ship social network into communities;

Step 5: Calculate the betweenness centrality of all ship nodes in the ship community network relative to any two communities. The betweenness centrality between communities represents the importance of ships as inter-community communication;

Step 6: Ships can access the intermediary status of each ship in the current ship network and the community membership of each ship in real time;

Step 7: When a ship carrying a data packet encounters a ship, it first communicates with the target ship to exchange the data packets carried by each other, and when the other party does not have the data packet carried by itself, it starts to judge whether to forward the program.

Preferably, the process of judging whether to forward or not in the step 7 is as follows: firstly judge that the other party is the destination ship of the data packet, if so, forward the data packet and deliver the data packet successfully; if the other party is not the destination ship, then judge whether it belongs to the same ship as the destination ship Community, if yes, forward it; otherwise, judge whether the value of the intermediary centrality of the other party to the community where the destination ship is located is greater than the value of itself to the destination community, if it is greater, forward it, otherwise do not forward it.

Preferably, the construction of the social network between ships needs to take the ship as a node and the social familiarity between the ships as an edge.

Preferably, the social familiarity between ships requires the calculation of historical encounters between ships, including the time stamp of the encounter, the location of the encounter, the state of the two ships at the time of the encounter, and the speed and duration of the two ships at the time of the encounter.

The present invention has the following beneficial effects:

The community-based ship network routing method introduces the social network analysis theory into the design of the distributed routing method of the ship self-organizing network, and mines and verifies the existence and characteristics of social features in the real ship network based on the large-scale GPS track records of real marine ships. , and apply it to the distributed multicast routing problem to improve the comprehensive transmission performance of multicast data communication in the ship's self-organizing network;

Compared with the principles of trajectory prediction, location greed, real-time topology discovery, random walk, and flooding based on traditional routing methods, the social characteristics of ship networks can better reflect the deep and long-term stable interaction laws and development trends in the network. Therefore, it has high reliability and practicability, and is more suitable for improving the comprehensive performance of data routing;

The routing method is designed according to the ship network, which is very suitable for the routing of the ship's self-organized network;

The routing method of the present invention abandons the idea of traditional routing, does not need to establish a transmission topology in advance, and does not need to maintain and rebuild the transmission topology. It can greatly reduce the transmission cost.

Description of drawings

Figure 1 is a schematic diagram of a ship's self-organizing network;

Fig. 2 is a schematic diagram of a community-based ship self-organizing network routing method;

Figure 3 is a comparison of five routing methods on the transmission cost;

Figure 4 is a comparison of five routing methods on the transmission delay.

Detailed ways

The specific embodiments of the present invention will be further described below in conjunction with the accompanying drawings and specific embodiments:

A community-based approach to ship network routing, including the following steps:

Step 1: The ship uploads the navigation information and the encounter information with other ships in a distributed manner through the communication at the time of encounter;

Step 2: The ship network platform calculates the social familiarity F(a, b) between ships according to the navigation information uploaded by the ship and the encounter information between ships. The specific calculation formula is shown in formula (1):

表示两条船相遇时的状态所对应的权重，当船a与船b相遇时都处在捕鱼状态时，则此相遇状态对a和b两条船之间的社交关系增益为α，当船a与船b相遇时都在航行则社交增益为β，如果两者相遇时状态不一样时，社交增益为γ，T表示两条船一段时间内总的相遇次数，τ表示某一相遇的持续时间；in,

Represents the weight corresponding to the state of the two boats when they meet. When boat a and boat b are both in fishing state when they meet, then this encounter state has a social relationship gain between the two boats a and b. When When ship a and ship b meet, they are both sailing, and the social gain is β. If the state of the two ships is different when they meet, the social gain is γ. T represents the total number of encounters between the two ships in a period of time, and τ represents a certain encounter. duration;

Step 3: Take ships as nodes, and use the social familiarity between ships F(a, b) as the weight of the edge to build a ship social network; use the historical ship sailing records to calculate the social familiarity between ships, and construct accordingly The ship social network divides the ship social network into ship communities, and decides whether to forward data packets according to the relationship between the neighboring ships and the community where the target ship is located. The construction of social network between ships needs to take the ship as the node and the social familiarity between the ships as the edge. Social familiarity between ships requires the calculation of historical encounters between ships, including the timestamp at the time of the encounter, the location at the time of the encounter, the state of the two ships at the time of the encounter (sailing, fishing, mooring, etc.), the two ships at the time of the encounter speed and duration.

Step 4: Use the community detection algorithm Louvain algorithm to divide the ship social network into communities;

Step 5: Calculate the betweenness centrality of all ship nodes in the ship community network relative to any two communities. The betweenness centrality between communities represents the importance of ships as inter-community communication;

The index of judging the intermediary communication ability of a ship relative to two communities - intermediary centrality, refers to the relationship between a certain ship in the ship network relative to a certain two communities.

Step 6: Ships can access the intermediary status of each ship in the current ship network and the community membership of each ship in real time;

Step 7: When a ship carrying a data packet encounters a ship, it first communicates with the target ship to exchange the data packets carried by each other, and when the other party does not have the data packet carried by itself, it starts to judge whether to forward the program.

The process of judging whether to forward is as follows: first, judge that the other party is the destination ship of the data packet, if so, forward it, and the data packet is delivered successfully; if the other party is not the destination ship, judge whether it belongs to the same community as the destination ship, and if so, forward it; Otherwise, it is judged whether the value of the intermediary centrality of the other party to the community where the destination ship is located is greater than the value of its own to the destination community, if it is greater, it will be forwarded, otherwise it will not be forwarded.

Figure 1 shows the communication scenario of the ship's ad hoc network at sea. Each ship carries a wireless device that can communicate, and this wireless device has a certain communication radius. When the two ships are close to a certain distance, the two ships can communicate and perform subsequent operations such as judging whether they need to exchange datagrams. For example, ship s wants to communicate with ship d, but the distance is too far, but ship s can currently communicate with e, so it can pass the data packet to e, and e will continue to pass the data packet until it encounters ship d.

Figure 2 shows the working principle diagram of the community-based ship self-organizing network routing method designed by the present invention. The ship V _s2 is a source node with communication requirements, and it generates a data packet that needs to be transmitted to the ship V _d2 . The source node V _s2 has two ships V _d and V _c within its communication radius, which can help it spread data packets, but through the judgment of the method of the present invention, the ship V _d is often used as a community that communicates with the target ship V _d2 . case, that the ship V _d has a higher value of betweenness centrality for the target community C ₁ . So the ship will deliver the data packet to V _d , and then the ship V _d will deliver the data to the target community C ₁ as soon as possible. After the data packet is delivered to the target community, the data packet will be delivered among all members of the community until the target vessel V _d2 is found.

Figure 3 shows the comparison of the transmission cost of five routing methods (Random Walk RW, Location Greedy, Flooding, Social Familiarity-based Routing Method FBR, and the Community-based Routing Method CBR of the present invention). The inventive method, referred to as the CBR effect, has obvious advantages over the classical flooding and random walking, and significantly reduces the transmission cost.

FIG. 4 shows the comparison of the transmission delay of five routing methods, wherein the method of the present invention is referred to as the CBR effect and shows basically the same delay effect as the fastest flooding method. It is illustrated that the method also significantly reduces the transmission cost under the condition of ensuring relatively fast transmission performance, which is exactly the goal and advantage of the present invention.

It should be noted that, in this document, relational terms such as first and second are only used to distinguish one entity or operation from another entity or operation, and do not necessarily require or imply any relationship between these entities or operations. any such actual relationship or sequence exists.

Of course, the above description is not intended to limit the present invention, and the present invention is not limited to the above examples. Changes, modifications, additions or substitutions made by those skilled in the art within the essential scope of the present invention should also belong to the present invention. The scope of protection of the invention.

Claims (2)

1. The ship network routing method based on the community comprises the following steps:

step 1: the ship uploads navigation information and encounter information with other ships in a distributed manner through communication during encounter;

step 2: the ship network platform calculates social familiarity F (a, b) among ships according to navigation information uploaded by ships and meeting information among the ships, and the specific calculation formula is shown as formula (1):

wherein,

representing the weight corresponding to the state when two ships meet, when the ship a meets the ship b, the ship a is in a fishing state, the gain of the social relationship between the ship a and the ship b in the meeting state is alpha, when the ship a meets the ship b, the ship a sails, the social gain is beta, if the states of the ship a and the ship b are different, the social gain is gamma, T represents the total meeting times of the two ships within a period of time, and tau represents the duration of a certain meeting;

and step 3: constructing a ship social network by taking ships as nodes and taking social familiarity F (a, b) among the ships as weight of edges;

and 4, step 4: dividing the ship social network into communities by using a community detection algorithm Louvain algorithm;

and 5: calculating the mediation centrality of all ship nodes in the ship community network relative to any two social intervals, wherein the mediation centrality of the social intervals represents the characteristic of the importance of the ship as social interval communication;

step 6: the ship can access the intermediation condition of each ship and the community attribution condition of each ship in the current ship networking in real time;

and 7: when a ship carrying a data packet encounters a ship, firstly, the ship communicates with the encountered ship to exchange the conditions of the data packets carried by the ship, and when the opposite side does not have the data packet carried by the opposite side, whether the data packet is forwarded or not is judged;

the process of judging whether to forward in step 7 is as follows: firstly, judging whether the opposite party is a destination ship of the data packet, if so, forwarding, and successfully delivering the data packet; if the opposite party is not the target ship, judging whether the opposite party and the target ship belong to the same community, and if so, forwarding; otherwise, judging whether the value of the mediation centrality of the opposite party to the community where the target ship is located is larger than the value from the opposite party to the target community, if so, forwarding, otherwise, not forwarding.

2. The community-based ship network routing method of claim 1, wherein the social familiarity between ships requires computation of historical encounter conditions between ships, including timestamp of encounter, location of encounter, status of two ships at encounter, speed and duration of two ships at encounter.

Images