Sage Journals: Discover world-class research

Abstract

With the increasing concern over marine applications in recent years, the technology of underwater wireless sensor networks has received considerable attention. In underwater wireless sensor networks, the gathered data are sent to terrestrial control center through multi-hops for further processing. Underwater wireless sensor networks usually consist of three types of nodes: ordinary nodes, anchor nodes, and sink nodes. The data messages are transferred from an ordinary node or an anchored node to one of the sink nodes by discrete hops. Data forwarding algorithms are at the core position of underwater wireless sensor networks, which determines data in what way to forward. However, the existing data forwarding algorithms all have problems that transmission delay is too high and delivery ratio is low. Thus, we propose a data forwarding algorithm based on estimated Hungarian method to improve delivery ratio and reduce transmission delay. The estimated Hungarian method is applied to solve the assignment problem in data forwarding process, where the anchor nodes receive the forwarding requests from ordinary nodes and optimize the waiting queue. By applying this method in underwater wireless sensor networks, data forwarding has great advantages in success rate and transmission delay, which has been validated by both analysis and simulation results.

Keywords

Underwater wireless sensor networks data forwarding estimated Hungarian method

Introduction

With the increasing concern over marine applications in recent years, the technology of underwater wireless sensor networks (UWSNs)^1,2 has received considerable attention. In UWSNs, the gathered data are sent to terrestrial control center through multi-hops for further processing. The UWSN technology has broad prospect in many marine applications, such as the early warning of underwater disasters, resource exploration, environmental monitoring, and surveillance. Specially, the UWSN communication is based on acoustic multi-hop mechanism and thus the underwater propagation delay cannot be negligible. As shown in Figure 1, an UWSN usually consists of three types of nodes: ordinary nodes, anchor nodes, and sink nodes. The ordinary nodes affected by environment (such as the water current) are inclined to move frequently, and the anchor nodes are pulled by anchored ropes. The data messages are transferred from an ordinary node or an anchored node to one of the sink nodes by discrete hops.

Figure 1.

An underwater wireless sensor network.

In traditional self-organized networks,³ the data transmission between nodes is relatively stable, and the routing path should be built prior to the data transmissions. However, with the influence of node mobility, sparse distribution of nodes, and the continuous variation of node distance, UWSN node links are easily interrupted frequently so that the transmissions cannot be guaranteed. Such network is of the opportunistic network architecture,^4,5 where mobile nodes transfer the data messages through opportunistic contacts in store-carry-forward mode.^6–8 Routing algorithms in opportunistic networks can be classified into single-copy routing and multi-copy routing. With regard to single-copy routing, the typical work is the FirstContact,⁹ which allows only single copy of the data message be disseminated at each forwarding process, leading to a high transmission delay and a low reliability although a low cost is required. The multi-copy routing algorithms, such as Spay and Wait¹⁰ and Epidemic,¹¹ disseminate multiple copies of the data message during a time cycle, and they are more suitable for the network with dynamic topology, because the delivery success rate is increased and the transmission delay is reduced, though the dissemination cost suffer a rise.

Hungarian method is applied to effectively solve the assignment problem, giving rise to many specific applications in the fields of finance, military, aviation, and so on.^12–14 Similarly, the data forwarding process can essentially be regarded as the process of allocating message copies for the next-hop nodes. By applying Hungarian method in UWSNs, the forwarding stability of network would be improved and then data forwarding efficiency would be enhanced. Kuhn¹⁵ proposed a latent space model based on Hungarian method in dynamic network, where questions in network would be framed and answered, thereby the network is more stable.

Although Hungarian method can get best results of data allocation, so as to maximize the data forwarding efficiency, the inefficiency and high consumption make it cannot be directly applied in the data forwarding of UWSNs. Thus, the traditional Hungarian method is improved and data forwarding algorithm based on estimated Hungarian method (DFAH) is proposed to solve the assignment problem in data forwarding process, where the anchor nodes receive the forwarding requests from ordinary nodes and optimize the waiting queue in which the data packets are waited to forward according to content in requests. The fuzzy strategy reduces the time complexity of obtaining the weight of processing matrix, and estimated principle reduces times of iteration. Thereby, the delivery success rate is improved, while the transmission delay is reduced, although to some extent, DFAH sacrifices the optimal assignment result.

Related research

Compared with traditional terrestrial sensor networks, the data forwarding issue in UWSNs faces more problems such as excessive transmission delay due to the underwater acoustic communication, the instability and destructibility of nodes caused by the severe underwater environment. An UWSN is a type of opportunistic networks, where the nodes move irregularly and the contacts among nodes are opportunistic.

To address the data forwarding issue, in ad hoc network,¹⁶ compares residual energy that in candidate forwarding nodes with in neighbor nodes of last-hop node, the data packets are forwarded if the former is higher, otherwise discarded. The algorithms balance energy load of nodes based on energy consumption, where actual underwater implementation is difficult because of high requirement of node positioning. A distributed running mechanism to evaluate the possibility that nodes meet has been proposed by Davis et al.,¹⁷ where data forwarding is judged by evaluated possibility. Each node stores a possibility table regarding the node encounters, which would be updated at begin of each regular time slot. According to possibility table, nodes that have low possibility would try to deliver message to where possibility is high, then deliver success rate of entire network would be enhanced accordingly. Unfortunately, the method occupies too much network resource for numerical calculation. Based on the work described in the literature^11,18 gets an improvement, message would be deleted when nodes receive confirmation signal or data buffer in nodes over preset threshold, where message flooding would be avoided and forwarding overhead would be reduced.

Unlike ad hoc network, controlling actual process of forwarding in UWSNs is more difficult. With special environment conditions in UWSNs, Yan et al.¹⁹ proposed depth-based routing (DBR). In process of forwarding, nodes fed back depth information themselves to nodes around, where merely forwards data to nodes that have depth lower than themselves. Moreover, process of forwarding would be controlled by depth information. However, data redundancy and energy consumption both are too huge. A coverage-preserving algorithm called LEACH-Coverage-U²⁰ is proposed upon traditional LEACH algorithms, where cluster head is elected by calculating effective cover rate, and it will be used to forwarding judgment, whereas randomness using this method to select cluster head is too high so that cannot often select optimized cluster head. Hop-by-hop vector-based forwarding (HH-VBF)²¹ forwards data based on vector parameters, where randomness is avoided by designing forwarding vectors for each node; however, sensing positioning of nodes is also a problem.

Hungarian method has advantages in solving the problems such as traffic control, trajectory tracking, production control, and others.^15,22,23 In this article, Hungarian method is applied to optimize the data forwarding paths through setting a forwarding weight matrix. Especially, the forwarding weight matrix is set based on the relative positions between the ordinary nodes and the anchor nodes rather than the absolute positions of nodes, and thus, the real-time position information is not required. Nonetheless, the Hungarian method cannot be directly applied because of calculation method and handling limitation, because for high-order matrix, using traditional Hungarian method to process would lead to higher processing delay and low efficiency. Thus, the article has an improvement upon estimation. Through estimation, algorithms become more increasingly viable for underwater environment. In Zhang,²⁴ the proposed power efficient routing (PER) protocol also adopts an estimation control principle, where the suitable forwarding nodes are selected according to the distance between nodes, residual energy of nodes, and transmitting angle of nodes. Despite that, in UWSNs, the real-time information collection is very difficult, and the propagation delay becomes extremely large from calculating the optimal solution with a high complexity, which leads to more energy consumption in the data forwarding process as well. To this end, this article proposes a DFAH, which takes into account influences of the UWSNs environment and improves the inadaptability of traditional Hungarian method in UWSNs.

Note that this work is an extension to our previous work, which has proposed conference paper titled “A Data Forwarding Algorithm based on Estimated Hungarian Method for Underwater Sensor Networks.”²⁵ In terms of original model, data packet format, algorithm steps, mathematical analysis, and simulations, this article has some changes.

Forwarding technology description

Estimated Hungarian method description

The basic thought of Hungarian method is to seek independent 1-element group in matrix with a certain matrix transformation, the thought of which is similar to compute the optimal set of binary graph in the graph theory. The traditional Hungarian method can be described as follows

min Z = \sum_{i = 1}^{n} \sum_{j = 1}^{n} C_{ij} X_{ij} {\begin{matrix} \sum X_{ij} = 1, j = 1, 2, 3, \dots, n \\ \sum X_{ij} = 1, i = 1, 2, 3, \dots, n \\ X_{ij} = 0 or 1 \end{matrix}

(1)

where Z represents optimal solution; i and j, respectively, represent row number and column number.

A new weight matrix $C^{*} = (C_{ij}^{*})_{nn}$ can be obtained by making each row or each column of the weight matrix $C = (C_{ij})_{nn}$ minus (or plus) a constant such as $u_{i}$ or $v_{j}$ . If $C_{ij}^{*} = C_{ij} - u_{i} - v_{j}$ , optimized value of them are equal. By equivalence principle, weight matrix is transformed until independent 0 elements in original matrix satisfy optimal value of original question.

In UWSNs, we find that the traditional Hungarian method cannot be directly applied into the data forwarding algorithm due to the following reasons: (1) first, the integral weight matrix is the requirement for calculating optimal value in the traditional Hungarian method; however, in underwater environment, the sensor nodes usually cannot gather real-time information to construct this matrix. Therefore, the weight matrix has to be constructed by an estimation strategy. (2) Second, with regard to the execution cost, the traditional Hungarian method needs repeated iterations to simplify the weight matrix, and some of the iterations are invalid, and all these lead to extremely large overhead and processing delay. Thus, this article proposes an estimated Hungary-based average-simplified strategy, where the order reduction is introduced to decrease the overhead and the delay from iterations.

Forwarding technology description

In architecture structure of UWSNs, the node consists of ordinary nodes, anchor nodes, and sink nodes. The movement ranges of ordinary nodes are larger than others, and the movement speed of ordinary nodes is faster. Moreover, the movement ranges of anchor nodes are always limited. Sink nodes floating on the water surface are responsible for collecting the data packets for further process.

As shown in Figure 2, in DFAH, the anchor nodes play the role of data forwarding agents due to their limited movement ranges. At the start of each time slot, anchor nodes detect the forwarding requests from neighboring ordinary nodes which are deeper. If some requests have been detected, the anchor node sends inquire_msg to the deeper ordinary nodes. On receiving the inquire_msg, each ordinary node replies with a respond_msg, which includes the information of movement speed, distance to the anchor node, residual capacity, and number of historical contacts.

Figure 2.

Forwarding model.

The number of historical contacts between node i and node j is marked as φ_ij is calculated as the number of average contacts among nodes

φ_{ij} = \frac{\sum_{n = k + l} a_{ij}^{n}}{m \cdot T_{n}}, l = 0, 1, 2, \dots, m, n \in N

(2)

where $a_{ij}^{n}$ represents the number of contacts between node i and j in nth time slot, and T_m is the length of each time slot.

After the anchor nodes receive the respond messages, where if the number of contacts is larger than the preset threshold, and if it is greater than reset value, they check the cache path. If it exists, forward data cache in a certain period first, because node mobile has regularity, and in general, node move in a certain range. Therefore, cache path is valuable to improve forwarding efficiency. Otherwise, if cache path does not exist, the forwarding weight $δ_{ij}$ is calculated to select next-hop node as

δ_{ij} = δ \cdot \frac{S_{i} \cdot φ_{ij}}{L_{ij} \cdot \sqrt[x]{E_{i}}}

(3)

where $S_{i}$ represents the speed of node i; L_ij represents the distance between ordinary node and anchor node; and E_i represents the number of data packets that residual buffer space can store, which must takes the xth root of $E_{i}$ to confine the impact of large value of $E_{i}$ on the forwarding weight. In simulation, the value of x is usually set to 3. δ is a balance coefficient for the forwarding weight. Specially, the case of δ = 0 indicates that the anchor node fails to obtain the integrated parameter information. δ is usually set to 1 in simulation. When the ordinary nodes move more rapidly, they are easier to move out of the anchor node’s communication range. Besides, the data packets should be forwarded as early as possible if the residual space is smaller.

By calculating forwarding weight, anchor node would get forwarding request that weight is different. At begin of each time slot, anchor node would handle forwarding requests that have been received. For anchor node, upper threshold number of processing requests of anchor node N_max would be set according to deployment density of nodes; when it is greater than N_max, sorts forwarding weight value and only reaches N_max forwarding requests would be handled. The purpose why it reaches N_max is needed because energy consumption and delay of the estimated Hungarian method both are high compared with broadcast when the number of candidate next-hops is too small.

Estimated matrix description

By calculating the forwarding weights, the anchor nodes would get the forwarding requests with different weights. At begin of each time slot, the anchor nodes handle the received forwarding requests. The maximum number of the requests can be processed by each anchor node is marked as N_max and set according to deployment density of nodes. If the number of received requests is larger than the preset N_max, these requests will be sorted through their forwarding weights, and the requests with larger weights will be preferentially processed.

Suppose that an anchor node has received n forwarding requests, and the number of ordinary nodes shallower than the anchor node in communication range is m (n ≤ m). The forwarding matrix C_m_× n is produced at the anchor node j, where the matrix element c_ij denotes the weight from an ordinary node i to another ordinary node j, and c_ij is calculated as

c_{ij} = δ_{ik} + δ_{jk}

(4)

According to the property, ordinary nodes around same anchor node have similar feature of moving range and moving speed. For calculating parameter that cannot be obtained timely, estimated strategy should be adopted. For instance, when calculating δ_ij, parameter S_i may lack, anchor node thus gets $\bar{S_{i}}$ to replace by taking the average of five S_i that are collected recently. We take 5% as reasonable error, testing in environment that has different node number by MATLAB tool, then compares weight that processed by estimated Hungarian method with standard weight. The difference in error range can be seemed as accurate, which can be shown as follow:

From Figure 3, accurate rate of estimated value decreased at the beginning and then kept nearly at 89%, fall at first is because order of processing matrix is smaller. Therefore, estimated method would be used, and finally, anchor node produces an estimated matrix C = (c_ij)_mn, which would produce 0-1 matrix through estimated Hungarian method. The method is shown below.

Figure 3.

Weight accuracy rate.

Therefore, the estimated method is used and thus an estimated matrix C = (c_ij)_mn is generated, which would be transformed into a 0-1 matrix through the estimated Hungarian method. The method detail is given as follows:

Row reduction: the average value of each row is calculated and then each element minus the average value of its row. As a special case, if the element is smaller than the average, then the element is set to 0.

Matrix marking: the row having the least 0 element should be found from top to bottom in the matrix. The first 0 element is selected from left to right in the found row. The related row and column of the selected 0 element are then marked for further processing. After that, the 0 elements in the marked row and column will not be taken as 0 elements in future. This step will be repeated until all rows and columns have been marked.

0-1 matrix production: the selected 0 elements are set as 1, and other elements are set as 0. Thus, the 0-1 matrix is produced.

For instance, the generated matrix $(\begin{matrix} 12 & 7 & 9 & 7 & 9 \\ 8 & 9 & 6 & 6 & 6 \\ 7 & 17 & 12 & 14 & 9 \\ 15 & 14 & 6 & 6 & 10 \\ 4 & 10 & 7 & 10 & 9 \end{matrix})$ can be transformed into $(\begin{matrix} 3 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 \\ 0 & 5 & 0 & 2 & 0 \\ 5 & 4 & 0 & 0 & 0 \\ 0 & 2 & 0 & 2 & 1 \end{matrix})$ by row reduction. Next, 0 element in the fifth row has the least 0 elements by top–bottom judgment, and thus, the first 0 element in this row is recorded so that can we can get $(\begin{matrix} 3 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 \\ 0 & 5 & 0 & 2 & 0 \\ 5 & 4 & 0 & 0 & 0 \\ 0 & 2 & 0 & 2 & 1 \end{matrix})$ , where the blue element represents 0 element and the red elements represent the elements in related row and column. Finally, the matrix $(\begin{matrix} 3 & 0 & 0 & 0 & 0 \\ 1 & 2 & 0 & 0 & 0 \\ 0 & 5 & 0 & 2 & 0 \\ 5 & 4 & 0 & 0 & 0 \\ 0 & 2 & 0 & 2 & 1 \end{matrix})$ can be obtained, and the transformed 0-1 matrix is expressed as $(\begin{matrix} 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 \end{matrix})$ .

Compared with traditional Hungarian method, in estimated Hungarian method, the iterative number is reduced greatly. Both time complexity and space complexity drop from O(n³) and O(n²) to O(n). Besides, such distribution forwarding can avoid congestion on some nodes.

Here, in the aspect of processing delay of matrix, we first use MATLAB tool to generate random matrix, then data of time consumption can be obtained by Hungarian method and estimated method as Figure 4 shows. From Figure 4, we can find that the plot gap between traditional Hungarian method and estimated Hungarian method become larger with the increase in matrix order.

Figure 4.

Processing delay figure.

To measure the performance of estimated Hungarian method in the issue of data forwarding, we define the efficiency value M considering calculated result and the processing time, and M is expressed as

M = \frac{1}{t_{n} \cdot \sum_{i = 1}^{n} \sum_{j = 1}^{n} {c'}_{ij} c_{ij}}

(5)

C = \sum_{i = 1}^{n} \sum_{j = 1}^{n} c'_{ij} c_{ij}

(6)

where $c_{ij}$ represents the element of weight matrix, $c'_{ij}$ is the element of weight matrix that has been processed by Hungarian method, and t_n denotes the length of processing time for handling the nth-order weight matrix.

Efficiency value M takes full account of processing time and optimized degree can be a good assessment basis for matrix processing. As shown in Figure 5, with the increase in matrix order, the efficiency value of estimated Hungarian method decreases sharply, but the plot of estimated Hungarian method is higher than that of traditional Hungarian method regardless of the matrix order. For higher efficiency, order of weight matrix should not be too high. Obviously, with low-order weight matrix, estimated Hungary method performs better.

Figure 5.

Efficiency value.

Forwarding strategy description

In the forwarding process, the ordinary nodes carry some generated data packets until they encounter the anchor nodes with shallower depths, and then, ordinary nodes send the forwarding requests to the anchor nodes. Anchor nodes sequentially process the received forwarding requests according to the weights of requests.

Afterward, the anchor nodes detect the neighboring ordinary nodes with shallower depths. Then, an estimated matrix is produced; on basis of that, 0-1 matrix is then obtained by the estimated Hungarian method.

Each forwarding node is related to a receiving node and called the primary receiving node. The receiving node with 0 elements in matrix is called the secondary receiving node. If the number of nodes is fewer than n, according to formula (4), then the data packets should be forwarded to the node with largest weight.

The anchor nodes play the role of forwarding agents, and thus, the data packets should be first sent to the anchor nodes which forward these packets to the upper ordinary nodes. Note that each anchor node should take a living-time process on basis of the obtained 0-1 matrix. With regard to the data packets to be forwarded to the primary receiving nodes or the secondary receiving nodes, the living-time should be set for each data packet to reduce network redundancy.

Once receiving the data packet by the destination node, the destination will broadcast an ack_msg to all the ordinary nodes and anchor nodes carrying the same data packet. The carried data packet will be discarded. The process of interaction between nodes is shown in Figure 6.

Figure 6.

Interaction sequence diagram.

The stability of anchor nodes is utilized in this forwarding strategy, and the anchor nodes are assigned to undertake the task of forwarding agents. Meanwhile, the forwarding process is optimized by an estimated Hungarian method, and the data redundancy is reduced by setting proper living-time for data packets. Besides, the ack_msg list is updated to enhance the forwarding efficiency and reduce the forwarding delay.

Mathematical analysis

Suppose the node coordinates obey the normal distribution: X∼N(μ₁, σ₁), Y∼N(μ₂, σ₂), Z∼N(μ₃, σ₂), and the sink node coordinate is (x_t, y_t, z_t), so the transmission distance $L = (\sqrt{{(μ_{1} - x_{t})}^{2} + {(μ_{2} - y_{t})}^{2} + {(μ_{3} - z_{t})}^{2}}) / φ$ and forwarding count T_c can be estimated as $\sqrt{{(μ_{1} - x_{t})}^{2} + {(μ_{2} - y_{t})}^{2} + {(μ_{3} - z_{t})}^{2}} / 2 φ R$ , where φ represents the forwarding loss and R is communication range of nodes.

The speed of acoustic wave is marked as S_t, and the transmission delay is expressed as

t_{d} = \frac{L}{S_{t}} = \frac{\sqrt{{(μ_{1} - x_{t})}^{2} + {(μ_{2} - y_{t})}^{2} + {(μ_{3} - z_{t})}^{2}}}{φ S_{t}}

(7)

From which it can be found that transmission delay is mostly affected by optimized degree of estimated Hungarian method and the positions of nodes.

Assume that order of weight matrix is n and the energy consumption of each forwarding process is e, and thus, the total energy consumption is calculated as

e_{t} = e . n^{T_{c}} = e . n^{\frac{\sqrt{{(μ_{1} - x_{t})}^{2} + {(μ_{2} - y_{t})}^{2} + {(μ_{3} - z_{t})}^{2}}}{2 φ R}}

(8)

Hence, the influence factors of energy consumption are similar to those of transmission delay, excepting the order of matrix.

With regard to the delivery success rate, without considering the unexpected cases such as node corruption, assume accidental rate of each forwarding process is a_r, then we can get delivery success rate as

d_{s} = {a_{r}}^{\frac{\sqrt{{(μ_{1} - x_{t})}^{2} + {(μ_{2} - y_{t})}^{2} + {(μ_{3} - z_{t})}^{2}}}{2 φ R}}

(9)

According to the above formula, the node density and accidental rate are the main factors affecting the performance of our proposed estimated Hungarian method.

Simulation

To verify the DFAH, it is realized on the platform of MyEclipse tool, and values of main parameters are given in Table 1. In this section, the indexes of node consumption, delivery success rate, and forwarding delay are observed while varying the value some simulation parameters. In addition, the performance DFAH is compared with DBR and HH-VBF.

Table 1.

Simulation parameters.

Parameter	Value
Volume of the deployment space	800 × 800 × 800 m³
The number of ordinary nodes	100
The number of sink nodes	10
Energy of sending data	80 μJ bit⁻¹
Energy of receiving a data packet	5 μJ bit⁻¹
Initial energy of node	100 J
Length of data packet	100 bits
Communication radius of node	20 m
Default processing order of estimated Hungarian method	4
Survival time of messages	15 s

Self-comparison simulation

Average transmission delay of nodes indicates the average value of time period from the generation of a data packet to its delivery. Average consumption represents the average value of consumption that node consumes in unit time slot, and delivery success rate represents the ratio of delivered data. First, the deployment space from 600 × 600 × 600 m³ to 1000 × 1000 × 1000 m³, and the number of nodes is varied from 10 to 40 with a step of 10.

From Figure 7(a), with the increase in deployment space size, the average transmission increases accordingly. This is because transmission distance becomes longer; however, with the number increase in anchor nodes, the transmission delay decreases. It shows that the anchor nodes undertake the forwarding agents, indicating that more anchor nodes can forward the data packets more effectively. Besides, the gap between the plots of anchor node number = 30 and anchor node number = 40 is very small, that is, the delay reduction becomes unobvious with the continuous number increase in anchor nodes. Similarly, the delivery success rate and average energy consumption are observed in Figure 7(b) and (c), respectively, which indicate that with the increase in deployment space size, the delivery success rate drops, and the energy consumption increases.

Figure 7.

Performance of DFAH versus number of anchor nodes, deployment space: (a) average transmission delay, (b) delivery success rate, and (c) average energy consumption.

Changing default processing order of Hungary matrix from 3 to 8, moreover, many tests were conducted simultaneously by changing the number of anchor nodes from 10 to 40, transmission delay, delivery success rate, and average energy consumption all are changed as following.

As shown in Figure 8(a), with processing order increases, transmission delay has a decreased trend; in addition, it would be stable gradually when order starts at 6. When order of matrix increases, it means the number of messages in every time piece would rise, so transmission delay shall reduce when order begin to rise. When processing order up to some degree, actually, such a large matrix is not needed in every time piece and thus delay begins to stable. In the aspect of delivery success rate as shown in Figure 8(b), the influence of estimated Hungarian method is low and is maintained at a stable value. For average energy consumption, high-order matrix needs more count times, so, with order of processing matrix increases, average energy up accordingly.

Figure 8.

Handling order comparison: (a) self-comparison of average transmission delay, (b) comparison of delivery success rate, and (c) comparison of average energy consumption.

According to varied data in figure, the use of forwarding technology has an positive influence on entire forwarding process; meanwhile, for UWSNs, the deployment number of anchor nodes has optimal value. Thus, for practical application, the deployment number of anchor nodes should approximate optimal value as far as possible.

Algorithm comparisons

In this section, the number of selected anchor nodes is set 20. With the increase in the node number, the delivery success rate, average transmission delay, and energy consumption are compared among the DFAH, DBR, and HH-VBF, and the results are given in Figure 9.

Figure 9.

Algorithm comparisons: (a) average energy comparison, (b) average transmission delay comparison, and (c) average transmission consumption comparison.

As shown in Figure 9(a), when more nodes are deployed, both DBR and DFAH maintain stable delivery success rates, which are around 82% and 78%, respectively. However, when the number of nodes falls into the interval [80,115], the delivery success rate has a rising trend. The reason is that the forwarding of HH-VBF rely on the node positions, when the node number in network is very few, the number of interactions and delivery success rate are very low accordingly. In term of average transmission delay, with the increase in node number, three forwarding patterns have downtrend and gradually stabilized. In such an opportunistic network, the rise of the node number enhances the contacting possibilities between nodes, which also improve the delivery success rate. If the nodes are deployed densely enough, the delivery success rate is very close to the peak value. As a result, the transmission delay becomes stable, which mainly benefits from the optimal processing. In the aspect of energy consumption, the large data redundancy will lead to higher energy consumption in DBR. For DFAH, the data redundancy is eliminated through the estimated Hungarian method and the ack_msg list updates, where the energy consumption of DFAH is reduced. Although lower energy consumption is achieved by HH-VBF, which adopts the single-copy forwarding strategy, delivery success rate is also extremely unsatisfactory.

Conclusion

In DFAH, the estimated Hungarian method is applied to solve the assignment problem in data forwarding process in UWSNs, where the anchor nodes receive the forwarding requests from ordinary nodes and optimize the waiting queue in which data packet is waited to forward according to request content. Therefore, DFAH has advantages in delivery success rate and transmission delay, moreover, energy consumption is also reasonable.

In future work, further optimization and improvement would be given for the processing method of weight matrix that reasonable energy consumption should be guaranteed.

Footnotes

Handling Editor: Jaime Lloret

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the National Key R&D Program of China under grant no. 2017YFB0802300; National Natural Science Foundation of China under grant nos 61373139, 41571389, and 61502250; and Postdoctoral Science Foundation of China under grant nos 2014M560379 and 2015T80484.

References

Darehshoorzadeh

Boukerche

. Underwater sensor networks: a new challenge for opportunistic routing protocols. IEEE Commun Mag 2015; 53(11): 98–107.

Capella

Bonastre

Ors

et al . A step forward in the in-line river monitoring of nitrate by means of a wireless sensor network. Sensor Actuat B: Chem 2014; 195(5): 396–403.

Akyildiz

Pompili

Melodia

. Underwater acoustic sensor networks: research challenges. Ad Hoc Netw 2005; 3(3): 257–279.

Huang

Lan

Tsai

. A survey of opportunistic networks. In: Proceedings of the 22nd international conference on advanced information networking and applications—workshops, Okinawa, Japan, 22–28 March 2008, pp.1672–1677. New York: IEEE.

Pelusi

Passarella

Conti

. Opportunistic networking: data forwarding in disconnected mobile ad hoc networks. IEEE Commun Mag 2006; 44(11): 134–141.

Chakchouk

. A survey on opportunistic routing in wireless communication networks. IEEE Commun Surv Tut 2015; 17: 2214–2241.

Zhao

Tang

et al . COUPON: a cooperative framework for building sensing maps in mobile opportunistic networks. IEEE T Parall Distr 2015; 26(2): 295–303.

Poonguzharselvi

Vetriselvi

. Survey on routing algorithms in opportunistic networks. In: Proceedings of the international conference on computer communication and informatics, Coimbatore, India, 4–6 January 2013, pp.1–5. New York: IEEE.

Jain

Fall

Patra

. Routing in a delay tolerant network. ACM SIGCOMM Comp Com 2004; 34(4): 145–158.

10.

Spyropoulos

Psounis

Raghavendra

. Spray and wait: an efficient routing scheme for intermittently connected mobile networks. In: Proceedings of the 2005 ACM SIGCOMM workshop on delay-tolerant networking, Philadelphia, PA, 26 August 2005, pp.252–259. New York: ACM.

11.

Vahdat

Becker

. Epidemic routing for partially-connected ad hoc networks. Technical report CS200006, 2000. Durham, NC: Duke University.

12.

Qian

et al . Research on resource scheduling method based on improved Hungary algorithm. In: Proceedings of the international conference on logistics engineering, Shenyang, China, January 2015. Atlantis Press.

13.

Shu

. The application of Floyed-Hungary method in solving problems concerning Chinese postman. J South China Univ of Trop Agric 2003; 9(2): 32–35.

14.

Lou

. The simplex method and the Hungary method in excel demonstration linear programming. J Bingtuan Educ Inst 2007; 17(6): 33–35.

15.

Kuhn

. Statement for naval research logistics: the Hungarian method for the assignment problem. J Royal Stat Soc 2015; 64(4): 611–633.

16.

Xiao

Peng Ji

Yang

. LE-VBF: lifetime-extended vector-based forwarding routing. In: Proceedings of the computer science & service system (CSSS), Nanjing, China, 11–13 August 2012, pp.1201–1203. New York: IEEE.

17.

Davis

Fagg

Levine

. Wearable computers as packet transport mechanisms in highly-partitioned ad-hoc networks. In: Proceedings of the international symposium on wearable computers, Zurich, 8–9 October 2001, pp.141–148. New York: IEEE.

18.

Burgess

Gallagher

Jensen

et al . MaxProp: routing for vehicle-based disruption-tolerant networks. In: Proceedings of the 25th IEEE international conference on computer communications, Barcelona, 23–29 April 2006, p.111. Washington, DC: IEEE Press.

19.

Yan

Shi

Cui

. DBR: depth-based routing for underwater sensor networks. In: International Ifip-tc6 networking conference on ad hoc and sensor networks, Singapore, 5–9 May 2008, pp.72–86. Berlin: Springer.

20.

Tsai

. Coverage-preserving routing protocols for randomly distributed wireless sensor networks. IEEE T Wirel Commun 2007; 6(4): 1240–1245.

21.

Nicolaou

See

Xie

et al . Improving the robustness of location-based routing for underwater sensor networks. In: Proceedings of the OCEANS, Aberdeen, 18–21 June 2007, p.16. New York: IEEE.

22.

Xiao

Lin

et al . Research of algorithm with Hungarian method in track correlation. Ship Electron Eng 2008; 28(10): 132–135.

23.

Mészáros

Budaváritakács

. Correlation between leadership effectiveness and personality preferences at a Hungarian independent financial advisor company. Pract Theory Syst Educ 2016; 11(1): 62–70.

24.

Zhang

Liang

Hou

et al . A power efficient routing protocol for wireless sensor network. In: Proceedings of the IEEE international conference on networking, sensing and control, London, 15–17 April 2007, p.2025. New York: IEEE.

25.

Wen

Liu

et al . A data forwarding algorithm based on estimated Hungarian method for underwater sensor networks. In: Proceedings of the 12th international conference on intelligent systems and knowledge engineering, Nanjing, China, 24–26 November 2017. New York: IEEE.

An estimated Hungarian method for data forwarding problem in underwater wireless sensor networks

Abstract

Keywords

Introduction

Related research

Forwarding technology description

Estimated Hungarian method description

Forwarding technology description

Estimated matrix description

Forwarding strategy description

Mathematical analysis

Simulation

Self-comparison simulation

Algorithm comparisons

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References