ON FINDING MINIMUM AND MAXIMUM PATH LENGTH IN GRID-BASED WIRELESS NETWORKS

International Journal of Wireless & Mobile Networks (IJWMN) Vol. 10, No. 1, February 2018
DOI: 10.5121/ijwmn.2018.10105 51
ON FINDING MINIMUM AND MAXIMUM PATH LENGTH
IN GRID-BASED WIRELESS NETWORKS
Faiza Al-Salti N. Alzeidi, Khaled Day and Bassel Arafeh
Department of Computer Science, Sultan Qaboos University, Oman
ABSTRACT
In this paper, we obtain the minimum and maximum hop counts between any pair of cells in the 3D grid-
based wireless networks. We start by determining the minimum path length between any two points in a 2D
grid coordinate system. We establish that the minimum path length is the maximum difference between the
corresponding coordinates of the two points. We then extend the result to derive the minimum and
maximum hop counts for the 3D grid-based wireless networks. We establish that the maximum path length
is the sum of the differences between the corresponding coordinates of the two cells. Whilst the minimum
path length depends on the positions of the two cells; it does not exceed the maximum difference between
the corresponding coordinates of the two cells.
KEYWORDS
Communication, wireless networks, 3D grid, hop count & path length
1. INTRODUCTION
The path length or hop count in a wireless network is the number of communication steps needed
to send a packet from a source node to a destination node in the network. Factors such as
transmission range, network topology, nodes’ mobility and routing protocols have a strong impact
on the path length [1]. The path length can affect the performance of the network. Specifically, it
has a direct impact on the packet delivery ratio, packet delay and energy consumption. The
studies in [2] [3] and [4] conducted mathematical analysis based on the path lengths to derive
upper bounds for the average packet delivery probability in wireless networks.
In [5], an algorithm for finding k shortest paths that link two points in a graph is proposed. The
algorithm can be used in finding paths that are of lengths less than a certain value. K. Day et al.
[6] considered finding a maximum number of node-disjoint paths of minimum or near minimum
lengths between any two points of the k-ary n-cube interconnection network. These paths are then
used to derive the fault diameter of the network. S. Basagni et al. [7] proposed a Channel Aware
Routing Protocol (CARP) for Underwater Wireless Sensor Networks (UWSNs). CARP uses a
hop count to decide the next forwarder. In [8], a dynamic programming model was developed to
compute the average path length of large scale-free networks, where the number of paths from a
given node exhibits a low power distribution.
The contribution of this paper is twofold. First, we derive the minimum path length between any
two points in a 2D grid coordinate system. We establish that the minimum path length between
any two points is the maximum difference between the corresponding coordinates of the two
points. Second, we use a similar strategy to derive the minimum and maximum path length
between any source-destination pair of cells for the 3D grid-based wireless networks. We
establish that the maximum path length is the sum of the differences between the corresponding
coordinates of the two cells. The minimum path length depends on the positions of the two cells;

52
thus, we consider all possible cases and calculate the minimum path length for each case. The
minimum path length does not exceed the maximum difference between the corresponding
coordinates of the two cells.
The rest of this paper is organized as follows. In section 2, we derive formulas for determining the
distance between any pair of points in a 2D grid coordinate system. Section 3 briefly presents the
3D grid-based topology for the wireless networks. A strategy similar to that used in section 2 is
used in section 4 to find the minimum and maximum path lengths of the 3D grid-based wireless
networks. Section 5 concludes the paper.
2. DETERMINING PATH LENGTH IN A 2D GRID COORDINATE SYSTEM
In this section, we demonstrate how to determine the minimum number of cells needed to move
from one point to another in a 2D grid coordinate system. Such a path is called a minimal path.
Consider the 2D grid coordinate system shown in Figure 1. There are up to 8 possible moves (i.e.
4 moves along the two axes and 4 diagonal moves) to move from one point to another. Let us
assume that the two points are A(x1, y1) and B(x2, y2). In general, we will refer to the number of
cells crossed by the minimal path as Hmin. Furthermore, the absolute difference between the two
points along an i-axis is referred to by δi. In other words, we denote δx = |x2-x1| and δy = |y2-y1|.
Lemma 1: Given two points A(x1, y1) and B(x2, y2) in a 2D grid coordinates system, for which
δx = δy, the number of grid cells crossed by the minimal path is given by:
Hmin = δx,
Proof: This case is shown in Figure 1. Recall that there are eight possible moves to neighboring
cells. A horizontal move or a vertical move reduces the Hamming distance (the Hamming
distance is being the sum of the differences between the corresponding coordinates) between the
two cells by one along the x-axis or the y-axis, respectively. Whereas a diagonal move reduces
the difference along each of the two dimensions by one. Thus, none of the 8 moves to
neighboring cells reduces the Hamming distance by more than two. Since the claimed minimum
path length is half of the Hamming distance (i.e. (δx + δy)/2 = δx), it is of minimum length.
Proposition 1: Given two points A(x1, y1) and B(x2, y2) in a 2D grid coordinates system, in
which δx ≠ δy. The number of grid cells crossed by the minimum path is given by:
Hmin = Maximum (δx, δy)
Proof: Let us assume that δx > δy as illustrated in Figure 2. Since δx > δy, we have δy (i.e.
Minimum (δx, δy)) diagonal moves that can give the highest reduction in the difference between
the two cells. After δy diagonal moves, δy will be zero, while δx will be reduced to (δx - δy).
Thus, we need (δx - δy) additional moves along the x-axis. Therefore, the maximum of the δx and
δy is the length of the minimal path. It is worth mentioning that the order of the moves is not
important, which means that different possible paths of minimal length can be obtained. Similar
proof can be stated for the case δy > δx. Hence, in general
Hmin = Maximum (δx, δy) □

Figure 1: Case 1 (δx = δy &
The same proving method will be used
maximum hops between any pair of source
networks.
3. OVERVIEW OF THE 3D
In this section, we briefly present the structure of the
networks are viewed as 3D grids (see
coordinates. The grid origin with (0, 0, 0) coordinates is assumed to be at the left forward corner
of the top surface as illustrated in
one cell can communicate directly with any node in the other cell. A cell can have up to 32
neighboring cells as shown in Figure
in each of the three dimensions (x, y and z) is
three dimensions. In addition, two cells are neighbors of each other if the difference along one
dimension is -2 or +2 and 0 along the other two dimensions. Therefore, the number of
neighboring cells of a cell is 33
-1 + 6 = 32. To a
is selected based on the nodes’ transmission range
We will use the notations x-1 or x+1 to refer to one move (one hop) to the left or to the right
along the x-axis, respectively. Furthermore,
move between two points which are two cells apart from each other to the left or to the right
along the x-axis, respectively. Similar notations are used for the y
the 32 neighboring cells are: (x
1,y,z+1), (x-1,y+1,z-1), (x-1,y+1,z), (x
(x,y,z+1), (x,y+1,z-1), (x,y+1,z), (x,y+1,z+1), (x+1,y
1), (x+1,y,z), (x+1,y,z+1), (x+1,y+1,z
2,z), (x,y+2,z), (x,y,z-2), (x,y,z+2).
A packet is forwarded on a cell-
node (i.e. final destination), which is
establish the maximum and minimum path lengths that connect any pair of source
δx = δy & δz = 0) Figure 2: Cas2 (δx > δy & δz = 0)
will be used in section 4 to derive the number of minimum
between any pair of source-destination cells in the 3D grid-based
D GRID-BASED WIRELESS NETWORKS
In this section, we briefly present the structure of the 3D grid-based wireless networks. Such
are viewed as 3D grids (see Figure 3 as an example). A cell is referred to by its (x, y, z)
of the top surface as illustrated in Figure 3. Two cells are neighbors of each other if any
unicate directly with any node in the other cell. A cell can have up to 32
Figure 4. That is a cell is a neighbor of another cell if the difference
in each of the three dimensions (x, y and z) is -1, 0 or +1 except when the difference is zero in all
2 or +2 and 0 along the other two dimensions. Therefore, the number of
1 + 6 = 32. To attain this reachability, the length of the cell side
transmission range R such that /2√3 [9].
1 or x+1 to refer to one move (one hop) to the left or to the right
respectively. Furthermore, we will use the notations x-2 or x+2 to refer to one
ween two points which are two cells apart from each other to the left or to the right
respectively. Similar notations are used for the y-axis and z-axis. Accordingly,
(x-1,y-1,z-1), (x-1,y-1,z), (x-1,y-1,z+1), (x-1,y,z-1), (x
1,y+1,z), (x-1,y+1,z+1), (x,y-1,z-1), (x,y-1,z), (x,y-1,z+1), (x,y,z
1), (x,y+1,z), (x,y+1,z+1), (x+1,y-1,z-1), (x+1,y-1,z), (x+1,y-1,z+1), (x+1,y,z
, (x+1,y+1,z-1), (x+1,y+1,z), (x+1,y+1,z+1), (x-2,y,z), (x+2,y,z), (x,y
2), (x,y,z+2).
-by-cell basis using cell neighboring moves until it reaches a sink
node (i.e. final destination), which is assumed to be located at a surface cell. In this paper, we will
establish the maximum and minimum path lengths that connect any pair of source-sink cells.
53
δ δz = 0)
the number of minimum and
based wireless
based wireless networks. Such
A cell is referred to by its (x, y, z)
wo cells are neighbors of each other if any node in
unicate directly with any node in the other cell. A cell can have up to 32
. That is a cell is a neighbor of another cell if the difference
fference is zero in all
2 or +2 and 0 along the other two dimensions. Therefore, the number of
ttain this reachability, the length of the cell side d
1 or x+1 to refer to one move (one hop) to the left or to the right
2 or x+2 to refer to one
ween two points which are two cells apart from each other to the left or to the right
axis. Accordingly,
1), (x-1,y,z), (x-
1,z+1), (x,y,z-1),
1,z+1), (x+1,y,z-
2,y,z), (x+2,y,z), (x,y-
neighboring moves until it reaches a sink
located at a surface cell. In this paper, we will
sink cells.

Figure 4: A cross section of the 32 neighboring cells [9]
4. PATH LENGTHS FOR THE
In this section, we will apply a similar strategy
minimum number of hops between any two cells
possible moves, and the destination cells are always assumed to be at the grid surface level where
the z-coordinate is equal to zero
cells by (sx, sy, sz) and (dx, dy,
the coordinates of the source and the
sx|, δy=|dy-sy| and δz=|dz|.
The maximum number of hops H
differences in the three dimensions.
that gives the smallest progress. In other words, selecting the neighbor that reduces the difference
in one dimension by only one, while keep
maximum path length is given by
The following is a possible path with maximum length:
1,
The length of the shortest path H
to the source cell. The different possible positions are shown in
Figure 3: A view of the 3D grid [9]
Figure 4: A cross section of the 32 neighboring cells [9]
HE 3D GRID STRUCTURE
apply a similar strategy as in section 2 to calculate the maximum and
minimum number of hops between any two cells in a 3D grid structure. Recall that there are 32
the destination cells are always assumed to be at the grid surface level where
. Let us denote the xyz-coordinates of the source and destination
y, dz), respectively. The absolute value of the difference
the coordinates of the source and the destination in the three dimensions are denoted by
Hmax is easy to determine. It is basically the sum of the
differences in the three dimensions. This can be explained by selecting, in each hop, the neighbor
progress. In other words, selecting the neighbor that reduces the difference
one, while keeping the other dimensions unchanged. Therefore, the
given by:

possible path with maximum length:
, , 1, , , 1
Hmin depends mainly on the position of the destination
to the source cell. The different possible positions are shown in Figure 5. From the cases shown i
54
to calculate the maximum and the
Recall that there are 32
the destination cells are always assumed to be at the grid surface level where
and destination
differences between
denoted by δx=|dx-
It is basically the sum of the absolute
This can be explained by selecting, in each hop, the neighbor
progress. In other words, selecting the neighbor that reduces the difference
Therefore, the
destination cell relative
. From the cases shown in

this Figure, there are different subcases based on the differences in the three dimensions
the source and destination cells as described below.
Figure 5: Different possible cases for the position of the
4.1. Case 1: sx = dx & sy = dy & sz > 0
In this case, the source and the
horizontal planes. The minimal path length is:
This length is achieved by moving the packet vertically
neighbor (x, y, z-2), until reaching
maximum reduction in the difference between the
available possible moves. Therefore
for moving a packet is given by:
4.2. Case 2: sx<=dx & sy<=dy
Case 2.1 δx = δy = δz:
This is achieved by moving the packet diagonally in the xyz
packet is moved along the following
We can justify that this path is
neighboring cells reduces the Hamming distance by more than 3. Since the length of this path is
equal to one third of the Hamming distance (i.e. (
Case 2.2 δx = δy & δz > δx:
, there are different subcases based on the differences in the three dimensions
cells as described below.
Different possible cases for the position of the destination cell relative to the source cell
4.1. Case 1: sx = dx & sy = dy & sz > 0
he source and the destination are in the same vertical column but
. The minimal path length is:
2
is achieved by moving the packet vertically 2 times along the z
reaching the target cell. Note that this is the best move (in terms of the
reduction in the difference between the coordinates of the two cells) among the
Therefore, the minimal path (in terms of the minimum number of hops)
, , # 2 $
4.2. Case 2: sx<=dx & sy<=dy
This is achieved by moving the packet diagonally in the xyz-space δx hops. In other words, the
the following path:
1, 1, # 1
is of minimum length by noticing that none of the 32 moves to
Hamming distance by more than 3. Since the length of this path is
equal to one third of the Hamming distance (i.e. (δx δy δz(/3 = δx(, it is of minimum length.
)
#
2
*
55
, there are different subcases based on the differences in the three dimensions between
cell relative to the source cell
are in the same vertical column but in different
along the z-axis via the
Note that this is the best move (in terms of the
two cells) among the
number of hops)
x hops. In other words, the
of minimum length by noticing that none of the 32 moves to
Hamming distance by more than 3. Since the length of this path is
, it is of minimum length.

56
The best possible move (yielding a maximum reduction in the Hamming distance) among the
available neighbors is a move to the diagonal neighbor in the xyz-space. This condition
remains valid for a number of δx hops. After that, the move <x, y, z-2> gives the best
reduction, and we need
+
$
such moves. Thus, we need at least
+
$
moves to
reach the destination cell. Since the order of the moves is not important, one possible path
will be:
1, + 1, − 1 > , < , , − 2 >
)
+
$
*

Case 2.3 δx = δy & δz < δx:
= + , − ( =
Initially, the best possible move among the available neighbors is a diagonal move in the
xyz-space. This condition stays valid for a number of δz hops. After that, the move in the xy-
plane <x+1, y+1, z> gives the maximum reduction in the Hamming distance, and we need
, − ( such moves. Thus, we need at least moves to reach the destination cell. One
possible path will be:
< + 1, + 1, − 1 > , < + 1, + 1, > +

Case 2.4 δz = δy & δz > δx
= + , − ( =
This is achieved by moving the packet diagonally in the xyz-space δx hops followed by (δz -
δx) moves in the yz-plane. Therefore, the path is as follows:
< + 1, + 1, − 1 > , < , + 1, − 1 > +
The proof of the optimality of this path is similar to the proof of Case 2.3 with swapping of z
and x.
Case 2.5 δz= δy & δz < δx
= + )
−
2
*
This is achieved by moving the packet diagonally in the xyz-space δz hops followed by
+
$
moves in the x-axis using the neighbor <x+2, y, z>. Therefore, the path is as follows:
< + 1, + 1, − 1 > , < + 2, , >
)
+
$
*

The proof of the optimality of this path is similar to the proof of Case 2.2 with swapping of z
and x.
Case 2.6 δx = δz & δz > δy
= , − ( + =

57
This is achieved by moving the packet diagonally in the xyz-space δy hops, followed by (δz-δy)
moves in the xz-plane. Therefore, the path is as follows:
< + 1, + 1, − 1 > , < + 1, , − 1 > +
Similar to the proof in the third subcase in Case 2, one can show that this path is of minimal path
length.
Case 2.7 δx = δz & δx < δy
= )
−
2
* +
This is achieved by moving the packet diagonally in the xyz-space δx hops. Then, moving it
along the y-axis
+
$
hops. Therefore, the path is as follows:
< + 1, + 1, − 1 > , < , + 2, >
)
+
$
*
The proof of the optimality of this case is similar to the proof of Case 2.2 swapping the roles of y
and z.
Case 2.8 δx ≠ δy, δy ≠ δz and δx ≠ δz:
To find the minimal path length in this sub case, we need to determine the maximum and the
second maximum among δx, δy and δz. For example, if the order in their values is as
follows:
δx > δy > δz; then:
= + , − ( + )
−
2
* = + )
−
2
*
This is achieved by moving the packet diagonally in the xyz-space δz hops, which is the best
move from the available moves. Then, moving in the xy-plane (δy-δz) hops, which is also
the best among the available moves. Finally, moving along the x-axis
+
$
hops. Thus,
the total number of hops is +
+
$
. Therefore, the path is as follows:
< + 1, + 1, − 1 > , < + 1, + 1, > +
, < + 2, , >
)
+
$
*
4.3. Case 3: sx<=dx & sy>dy
The subcases are similar to those in case 2 except case 2.1when all deltas are equal, which is not
part of this case. Thus, the path lengths of similar subcases are equal. However, the plus sign of
the y coordinate is changed to negative sign.
4.4. Case 4: sx>dx & sy<=dy
part of this case. The path lengths of similar subcases are equal. However, the plus sign of the x
coordinate is changed to negative sign.

58
4.5. Case 5: sx>dx & sy>dy
part of this case. The path lengths of similar subcases are equal. However, the plus sign of the x
and y coordinates are changed to negative signs.
5. CONCLUSION
In this paper, we have first derived the length of the shortest paths connecting any two points in a
2D grid coordinate system. The obtained result shows that the path length is equal to the
maximum difference between the corresponding coordinates of the two points. We have then
used a similar approach to determine the maximum and minimum path lengths between any pair
of cells with a characterization of the corresponding paths for the 3D grid-based wireless
networks. Each cell has up to 32 neighboring cells as described earlier. We have proved that the
maximum path length is the sum of the differences between the corresponding coordinates of the
two cells. The minimum path length depends on the positions of the two cells; though, not
exceeding the maximum difference between the corresponding coordinates of the two cells. These
results can be used to design routing protocols based on the 3D grid structure.
ACKNOWLEDGMENT
This work is supported by The Research Council (TRC) of the Sultanate of Oman under the
research grant number RC/SCI/COMP/15/02.
REFERENCES
[1] A. Pal, J. P. Singh, and P. Dutta, “Path length prediction in MANET under AODV routing:
Comparative analysis of ARIMA and MLP model,” Egyption Informatics Journal, vol. 16, no. 1, pp.
103–111, March 2015.
[2] K. Day, a. Touzene, s. Harous, and b. Arafeh, “a reliable multipath routing protocol for mobile ad-hoc
networks: adapting techniques from interconnection networks,” journal of interconnection networks,
vol. 12, no. 01n02, pp. 19–54, march 2011.
[3] K. Day, A. Touzene, B. Arafeh, and N. Alzeidi, “PARALLEL ROUTING IN MOBILE AD-HOC
Networks,” International Journal of Computer Networks & Communications (IJCNC), vol. 3, no. 5,
pp. 77–94, September 2011.
[4] F. Al-Salti, N. Alzeidi, and B. Arafeh, “A New Multipath Grid-Based Geographic Routing Protocol
for Underwater Wireless Sensor Networks,” in 2014 International Conference on Cyber-Enabled
Distributed Computing and Knowledge Discovery, 13-15 October 2014, pp. 331–336, Shanghai,
China.
[5] D. Eppstein, “Finding the k shortest paths,” SIAM journal on computing, vol. 28, no. 2, pp. 652–673,
1998.
[6] K. Day and A. E. Al-Ayyoub, “Fault diameter of k-ary n-cube networks,” IEEE Transactions on
Parallel and Distributed Systems, vol. 8, no. 9, pp. 903–907, September 1997.
[7] S. Basagni, C. Petrioli, R. Petroccia, and D. Spaccini, “CARP: A Channel-aware routing protocol for
underwater acoustic wireless networks,” Ad Hoc Networks, vol. 34, pp. 92-104, November 2015.

59
[8] G. Mao and N. Zhang, “Analysis of Average Shortest-Path Length of Scale-Free Network,” Journal of
Applied Mathematics, vol. 2013, pp. 1–5, July 2013.
[9] F. Al-Salti, N. Alzeidi, K. Day, B. Arafeh, and A. Touzene, “Grid-based Priority Routing Protocol for
UWSNS,” International Journal of Computer Networks and Communications, vol. 9, no. 6, pp. 1–20,
November 2017.

ON FINDING MINIMUM AND MAXIMUM PATH LENGTH IN GRID-BASED WIRELESS NETWORKS

Recommended

More Related Content

What's hot (17)

Similar to ON FINDING MINIMUM AND MAXIMUM PATH LENGTH IN GRID-BASED WIRELESS NETWORKS (20)

Recently uploaded (20)

ON FINDING MINIMUM AND MAXIMUM PATH LENGTH IN GRID-BASED WIRELESS NETWORKS