# A Quasistraight Line Routing Protocol for Square Grid-Based Wireless Sensor Networks

Authors: Md. Ajij; Sanjoy Pratihar; Ashish Kumar Luhach; Diptendu Sinha Roy
Journal: Wireless Communications and Mobile Computing
 (2022)

---

## Abstract

Sensor nodes in a wireless sensor network (WSN) are both energy-constrained and vulnerable to faults and disasters. Communication between the sensor nodes is generally hop-by-hop, and the nodes are distributed throughout the area to be covered. Broadcast-based routing protocols are not preferable in sensor networks since broadcasting is considered costly in terms of battery power consumption. In this paper, a digital quasistraight line segment- (DQSS-) based approach is employed for the detection of quasistraight line segments, i.e., for quasistraight path finding between WSN sensors arranged in a square grid. Comparative results show that the method is comparable with the best-known straight line finding algorithm in terms of path lengths and computation time. Moreover, the proposed method is capable of avoiding dead nodes by updating DQSS parameters dynamically during path finding. Hence, the proposed method is promising to be used in WSN square grids as a quasistraight line routing protocol.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) are extensively used in monitoring environments, surveillance equipments, intelligent home appliances operated remotely, patient care systems, etc. In WSN, the sensor nodes establish the path for communication from the sender to the receiver. This path making process should be carried out with limited resources. The performance of WSN is generally affected by many factors. These affecting factors are bandwidth, mobility, scalability, data aggregation, power consumption, etc. Because nodes have limited power sources, the minimization of power consumption is a vital issue in WSN, and this defines the performance of WSN [1]. Maximum energy is consumed by the sensor nodes in the communication processes. Routing protocols should be robust and straightforward, ensuring less energy consumption. Because of the limited resources of WSN nodes, the routing protocols must support the extended lifespan of the nodes [2]. Therefore, many protocols have been proposed highlighting the minimization of energy consumption.Different protocols have been developed for WSNs according to the different prerequisites of uses and a large number of WSNs types. Numerous studies have attempted to analyze and classify these routing protocols according to different parameters that have been published. WSN routing protocol can be classified based on (a) application type, (b) delivery mode, (c) network architecture, (d) initiator of communication, (e) path establishment (route discovery), (f) network topology, (g) protocol operation, (h) next hop selection, and (i) latency-aware energy-efficient routing. The main goal of WSN is to establish a path consisting of the WSN nodes which will be reliable and energy efficient [3]. Energy consumption in routing is mainly due to finding neighbors for communications and necessary small computations. So, usually, the routing algorithms focus on how to compute the shortest path from the source node to the destination for quick transmission. A quick shortest path finding from the source node to sink may reduce the network congestion also.Most of the traditional routing protocols cannot avoid the construction of curved (nonstraight) paths for data transmission. As a result, many multidirectional communications will lead to wastage of energy. Furthermore, the nonstraight paths normally contain more nodes than the straight paths, which leads to higher energy consumption [4]. So it is worthy of finding out a straight-line route (path).Another serious problem is the recovery of failure nodes in the WSN environment. Node failure may be because of many reasons. The most crucial reasons for node failure in a wireless sensor network (WSN) [5] are (a) fabrication process problems, (b) environmental factors, (c) battery power depletion, and (d) enemy attacks. Node failure is a common issue in WSN, and this affects the connectivity in a network, which degrades the quality of communication [6]. In WSN, a connected network is desired for smooth communication. Hence, restoring connectivity is always given importance. Connectivity restoration is normally done by replacing dead nodes with other unused nodes [7]. This replacement mechanism should be robust, and the computational overhead must be taken care of as high-cost computations reduce the battery life [8–10]. WSNs and ad hoc networks are also vulnerable to faults, often disasters, and, owing to this very nature, are expected to fail and subsequently recover from such scenarios with minimal extraneous support [11, 12]. Energy optimal WSN operations have been studied extensively over the years, and the topologies and management strategies vary drastically with WSN use cases and applications [13, 14]. Various routing protocols have been studied, each with its own set of pros and cons. It has been well understood that traditional distributed routing involving broadcasts or those employing geographic information via GPS modules are not suited due to excessive battery drainage [4, 15–17]. This has paved the path for probabilistic routing such as gossip [18] and random routing [19, 20]. However, such probabilistic routing techniques are unsuited for WSNs with a considerable number of nodes as they cannot guarantee straight line paths, thus cannot ensure minimum distance, and are hence suboptimal in terms of energy expended while routing.


### 1.1. Straight Line Routing

The random walk-based protocol is extensively used in WSN. Gossip [21] and rumor [20] are two well-known random walk-based routing protocols. Gossip concentrates on multicast, which suffers from power limitations and a high rate of wireless channel failure. In the rumor routing (RR) protocol, each node must maintain its list of neighbors. For propagation of a message, the node adds its list of neighbors to that message. Also, the message may keep track of all the nodes that this message has passed through. The node can decide a neighboring node to be the next node in the path. The next node must not have received the message earlier, and this way, it may prevent the route from growing in the backward direction. Rumor routing may show spiraling problems and energy is wasted in maintaining the records of visited nodes.Chou et al. [22] proposed a routing protocol based on a random walk and straight line routing (SLR), intending to extend the route as straight as possible. The central idea of the SLR protocol was creating the routing path hop-by-hop. In each hop, the next node is selected so that it lies on the extended straight path approximately. Liu et al. [4] proposed a new protocol based on straight line routing. The rumor routing (RR) protocol also solves the spiral problem. The basic idea of discovering the straight path was to find the angle using radio signals. Many routing protocols are specially designed to enhance the classic RR protocol. For example, DRR [23], IDRR [24], SDRR [25], and ZRR [26] have been proposed to solve the spiral problem. Improved sensor node localization technique is proposed by Phoemphon et al. [27], where the positions of the anchor nodes form a straight or nearly straight line. Banimelhem et al. [28] proposed a principal component analysis- (PCA-) based efficient path generation algorithm.


### 1.2. Faulty Node

Numerous strategies have been proposed for node deployment, which is often divided into two categories: random deployments and deterministic (grid-based) deployments [29]. Nodes are randomly eliminated and managed during ad hoc deportation in a stochastic deployment. When deploying on a grid, the nodes are arranged according to the angles of the grid points, which leads to greater accuracy in overall management. The physical positioning of sensor devices is better understood in grid-based deployment.Many works exist to detect and analyze faulty nodes, and a few of them are listed below. Guo et al. [30] propose a sequence-based mechanism for detecting defective nodes. An algorithm for identification of fault node, based on a statistical z-score function, is proposed in [31], where all sensor nodes deliberately send information to the central node, and the root node analyzes the data to identify the fault. Asim et al. [32] provide an architecture for the management of faults in wireless sensor networks. They proposed that the entire network can be partitioned into the virtual lattice of cells and subsequently perform fault detection and recovery locally with the least energy utilization. A genetic algorithm- (GA-) based technique was proposed by Rajeswari and Neduncheliyan [33].


## 1.1. Straight Line Routing

The random walk-based protocol is extensively used in WSN. Gossip [21] and rumor [20] are two well-known random walk-based routing protocols. Gossip concentrates on multicast, which suffers from power limitations and a high rate of wireless channel failure. In the rumor routing (RR) protocol, each node must maintain its list of neighbors. For propagation of a message, the node adds its list of neighbors to that message. Also, the message may keep track of all the nodes that this message has passed through. The node can decide a neighboring node to be the next node in the path. The next node must not have received the message earlier, and this way, it may prevent the route from growing in the backward direction. Rumor routing may show spiraling problems and energy is wasted in maintaining the records of visited nodes.Chou et al. [22] proposed a routing protocol based on a random walk and straight line routing (SLR), intending to extend the route as straight as possible. The central idea of the SLR protocol was creating the routing path hop-by-hop. In each hop, the next node is selected so that it lies on the extended straight path approximately. Liu et al. [4] proposed a new protocol based on straight line routing. The rumor routing (RR) protocol also solves the spiral problem. The basic idea of discovering the straight path was to find the angle using radio signals. Many routing protocols are specially designed to enhance the classic RR protocol. For example, DRR [23], IDRR [24], SDRR [25], and ZRR [26] have been proposed to solve the spiral problem. Improved sensor node localization technique is proposed by Phoemphon et al. [27], where the positions of the anchor nodes form a straight or nearly straight line. Banimelhem et al. [28] proposed a principal component analysis- (PCA-) based efficient path generation algorithm.


## 1.2. Faulty Node

Numerous strategies have been proposed for node deployment, which is often divided into two categories: random deployments and deterministic (grid-based) deployments [29]. Nodes are randomly eliminated and managed during ad hoc deportation in a stochastic deployment. When deploying on a grid, the nodes are arranged according to the angles of the grid points, which leads to greater accuracy in overall management. The physical positioning of sensor devices is better understood in grid-based deployment.Many works exist to detect and analyze faulty nodes, and a few of them are listed below. Guo et al. [30] propose a sequence-based mechanism for detecting defective nodes. An algorithm for identification of fault node, based on a statistical z-score function, is proposed in [31], where all sensor nodes deliberately send information to the central node, and the root node analyzes the data to identify the fault. Asim et al. [32] provide an architecture for the management of faults in wireless sensor networks. They proposed that the entire network can be partitioned into the virtual lattice of cells and subsequently perform fault detection and recovery locally with the least energy utilization. A genetic algorithm- (GA-) based technique was proposed by Rajeswari and Neduncheliyan [33].


## 2. Our Contributions

In this work, we have proposed a novel path finding method based on quasistraight line fitting focusing on the grid-based deployment of sensor nodes. Moreover, we have proposed a protocol for path making and avoiding faulty nodes in a square grid of sensor nodes during path making. The protocol establishes a quasistraight line routing protocol for a node to node communication, involving a minimum possible number of sensors. We assume that there will be a few dead nodes in the sensor grid (mostly they are either live or sleeping). This proposed path making is fast and dynamic, and avoiding dead nodes does not incur extra communication costs.


## 3. Digital Quasistraight Line Segment (DQSS)

The structural view of rectangular grid-based wireless sensor network and points in digital space are indistinguishable. In our proposed work, our objective is to fit quasistraight digital line segments in the rectangular grid to find out the shortest path between two endpoints (source and destination) in WSN. The shortest distance between two points is indeed a straight line. In grid-based WSN, digital straight line will be suitable to explore the shortest route from sender to receiver.Characterizations of digital straight lines have been given in many ways till date [34, 35]. Moreover, many algorithms exist to verify whether a given thin arc is digitally straight or not. Freeman introduced the chain code-based technique for representing 8 connected arcs and lines as a sequence of straight pieces [36, 37]. A chain code sequence (representing a digital curve) should possess the following properties if it represents a digital straight line segment (DSS) [34].
(i)
(R1) The runs have at most two directions, differing by 45°, and for one of these directions, the run length must be 1(ii)
(R2) The runs can have only two lengths, which are consecutive integers(iii)
(R3) One of the runs can occur only once at a time(iv)
(R4) For the run length that occurs in runs, these runs can themselves have only two lengths, which are consecutive integersIn this proposed work, we characterize a straight line segment as the chain code sequence:npsnqsnp⋯, where n is nonsingular code (the code occurs consecutively multiple times) and s is singular code (occurs singly in between nonsingular codes’ runs). Code values, n and s, are consecutive integer differing by 45°. In our consideration, the nonsingular run lengths, p and q, are consecutive integers. Property R1 and R2 hold in our cases. On property R3, we are specific, because in our method, none of the runs occurs in runs. Instead, both the run lengths repeat alternately. So, it is evident that we may not always reach the destination point D. Whenever we reach the row or the column of the destination point in the grid, we use a horizontal or vertical stretch from that point to the destination point (D). Hence, we refer to the digital straight line segments obtained by us as digital quasistraight line segments (DQSS).An example of a DQSS is shown in Figure1, and the corresponding chain code is shown in Table 1. In Freeman’s chain code-based properties, the mentioned run length refers to the length of a continuous sequence of the nonsingular code (in the chain code sequence). In our discussion, we have used it as the number of points in the continuous sequence in single direction. In the example shown in Figure 1, as per Freeman’s definition, the two run lengths are l1=2 and l2=3, singular code s=1, and nonsingular code n=0. For the same example, we are considering the two run lengths l1=3 and l2=4.Figure 1
An example of a digital quasistraight line segment with singular codes=1, nonsingular code n=0, and the two run lengths (number of points in the run) l1 and l2 are 3 and 4, respectively.Table 1
Freeman’s chain code for the line segment shown in Figure1.
p000100010010001001000


### 3.1. Sixteen Directional DQSSs and Selection of DQSS

A digital quasistraight line segment will fall into one of the sixteen directional clusters as shown in Figure2. Given the two endpoints Sx1,y1 and Dx2,y2 of a segment, the direction can be determined in Table 2. The singular and nonsingular codes concerning the various directions are as follows: D1:s=1, n=0; D2:s=0, n=1; D3:s=2, n=1; D4:s=1, n=2; D5:s=3, n=2; D6:s=2, n=3; D7:s=4, n=3; D8:s=3, n=4; D9:s=5, n=4; D10:s=4, n=5; D11:s=6, n=5; D12:s=5, n=6; D13:s=7, n=6; D14:s=6, n=7; D15:s=0, n=7; and D16:s=7, n=0. Next, we find the number of steps, Scount, in the straight line segment, using Table 2 and do the followings to estimate the run lengths l1 and l2.
(i)
Break the number of steps,Scount, into two integers such that, Scount=k+m, where 0≤k−m≤1(ii)
If the DQSS has run lengths,l1 and l2 then check the following criteria: Slength≤k×l1+m×l2 and Slength⟵maxdx,dy(iii)
Select the DQSS which has minimum difference betweenSlength and (k×l1+m×l2)Figure 2
The sixteen directional DQSSs (representative segments withl1=4, l2=5).Table 2
Direction understanding based on coordinates of the endpoints.
X-coordinate signY-coordinate signdy<dxdy<dx2dx<dy2No. of stepsDirectionPositivePositiveYesYesNody+1D1PositivePositiveYesNoNodx−dy+1D2PositivePositiveNoNoNody−dx+1D3PositivePositiveNoNoYesdx+1D4NegativePositiveNoNoYesdx+1D5NegativePositiveNoNoNody−dx+1D6NegativePositiveYesNoNodx−dy+1D7NegativePositiveYesYesNody+1D8NegativeNegativeYesYesNody+1D9NegativeNegativeYesNoNodx−dy+1D10NegativeNegativeNoNoNody−dx+1D11NegativeNegativeNoNoYesdx+1D12PositiveNegativeNoNoYesdx+1D13PositiveNegativeNoNoNody−dx+1D14PositiveNegativeYesNoNodx−dy+1D15PositiveNegativeYesYesNody+1D16Our proposed DQSS-based quasistraight line finding method is shown in Algorithm1. The algorithm selects the grid points or nodes to show the DQSS connectivity from the source node (Si,j) to the destination node (Du,v). The proposed algorithm selects and activates the nodes lying on the selected DQSS by maintaining the proper direction of the DQSS (following the properties as stated earlier), i.e., using the values l1 and l2 alternately starting from the source S and using the singular and nonsingular codes s and n as applicable. To start the path, we start with the smaller run length at source S. The selection of l1, l2, s, and n is shown in Algorithm 1 and the path making is shown in procedure FIND PATH (Procedure 1) of Algorithm 1.Algorithm 1: DQSS-based routing algorithm.
Input: Geographical grid location of Source node (S) and Destination node (D)Output: N: A quasistraight path fromS to D.1 Translate the source node(Si,jfrom i,j to 0,0;2 Translate the destination node Du,v accordingly;3 Check x-coordinate sign, y-coordinate sign, if dy<dx, if dy<x/2, if dx<y/2;4 Find the applicable row in Table 2 and get directional codes: s (singular code) and n (nonsingular code); See. Fig. 25 Find the number of steps Scount and direction of DSS;6 Break the Scount in into two integers;Scount=k+m;(where 0≤k−m≤1);7 Find the two run-lengths l1 and l2using the following criteria:Slength⟵maxdx,dy;Slength≤k×l1+m×l2; Select l1 and l2when it shows minimum difference between Slength and k×l1+m×l2.8 N=Find-Pathl1,l2,s,n;Procedure 1: Find path l1,l2,s,n.
1 pcurr⟵S;N⟵∅;Run⟵odd;index⟵12 whilepcurr..x≠D.xANDpcurr.y≠D.ydo3   N=N∪pcurr;4   if Run=odd then5     limit⟵l16   else7     limit⟵l28   while index ≤ limit do9     pcurr⟵Point in the direction n from pcurr;10    N=N∪pcurr;11    index⟵index+112  if Run=odd then13    Run⟵even;14  if Run = even then15    Run⟵odd;16  pcurr⟵Point in the direction s from pcurr;17  index⟵1;18 if pcurr≠D then19 Extend vertically or horizontally from pcurr to D and condiser the points in N20 return N;


## 3.1. Sixteen Directional DQSSs and Selection of DQSS

A digital quasistraight line segment will fall into one of the sixteen directional clusters as shown in Figure2. Given the two endpoints Sx1,y1 and Dx2,y2 of a segment, the direction can be determined in Table 2. The singular and nonsingular codes concerning the various directions are as follows: D1:s=1, n=0; D2:s=0, n=1; D3:s=2, n=1; D4:s=1, n=2; D5:s=3, n=2; D6:s=2, n=3; D7:s=4, n=3; D8:s=3, n=4; D9:s=5, n=4; D10:s=4, n=5; D11:s=6, n=5; D12:s=5, n=6; D13:s=7, n=6; D14:s=6, n=7; D15:s=0, n=7; and D16:s=7, n=0. Next, we find the number of steps, Scount, in the straight line segment, using Table 2 and do the followings to estimate the run lengths l1 and l2.
(i)
Break the number of steps,Scount, into two integers such that, Scount=k+m, where 0≤k−m≤1(ii)
If the DQSS has run lengths,l1 and l2 then check the following criteria: Slength≤k×l1+m×l2 and Slength⟵maxdx,dy(iii)
Select the DQSS which has minimum difference betweenSlength and (k×l1+m×l2)Figure 2
The sixteen directional DQSSs (representative segments withl1=4, l2=5).Table 2
Direction understanding based on coordinates of the endpoints.
X-coordinate signY-coordinate signdy<dxdy<dx2dx<dy2No. of stepsDirectionPositivePositiveYesYesNody+1D1PositivePositiveYesNoNodx−dy+1D2PositivePositiveNoNoNody−dx+1D3PositivePositiveNoNoYesdx+1D4NegativePositiveNoNoYesdx+1D5NegativePositiveNoNoNody−dx+1D6NegativePositiveYesNoNodx−dy+1D7NegativePositiveYesYesNody+1D8NegativeNegativeYesYesNody+1D9NegativeNegativeYesNoNodx−dy+1D10NegativeNegativeNoNoNody−dx+1D11NegativeNegativeNoNoYesdx+1D12PositiveNegativeNoNoYesdx+1D13PositiveNegativeNoNoNody−dx+1D14PositiveNegativeYesNoNodx−dy+1D15PositiveNegativeYesYesNody+1D16Our proposed DQSS-based quasistraight line finding method is shown in Algorithm1. The algorithm selects the grid points or nodes to show the DQSS connectivity from the source node (Si,j) to the destination node (Du,v). The proposed algorithm selects and activates the nodes lying on the selected DQSS by maintaining the proper direction of the DQSS (following the properties as stated earlier), i.e., using the values l1 and l2 alternately starting from the source S and using the singular and nonsingular codes s and n as applicable. To start the path, we start with the smaller run length at source S. The selection of l1, l2, s, and n is shown in Algorithm 1 and the path making is shown in procedure FIND PATH (Procedure 1) of Algorithm 1.Algorithm 1: DQSS-based routing algorithm.
Input: Geographical grid location of Source node (S) and Destination node (D)Output: N: A quasistraight path fromS to D.1 Translate the source node(Si,jfrom i,j to 0,0;2 Translate the destination node Du,v accordingly;3 Check x-coordinate sign, y-coordinate sign, if dy<dx, if dy<x/2, if dx<y/2;4 Find the applicable row in Table 2 and get directional codes: s (singular code) and n (nonsingular code); See. Fig. 25 Find the number of steps Scount and direction of DSS;6 Break the Scount in into two integers;Scount=k+m;(where 0≤k−m≤1);7 Find the two run-lengths l1 and l2using the following criteria:Slength⟵maxdx,dy;Slength≤k×l1+m×l2; Select l1 and l2when it shows minimum difference between Slength and k×l1+m×l2.8 N=Find-Pathl1,l2,s,n;Procedure 1: Find path l1,l2,s,n.
1 pcurr⟵S;N⟵∅;Run⟵odd;index⟵12 whilepcurr..x≠D.xANDpcurr.y≠D.ydo3   N=N∪pcurr;4   if Run=odd then5     limit⟵l16   else7     limit⟵l28   while index ≤ limit do9     pcurr⟵Point in the direction n from pcurr;10    N=N∪pcurr;11    index⟵index+112  if Run=odd then13    Run⟵even;14  if Run = even then15    Run⟵odd;16  pcurr⟵Point in the direction s from pcurr;17  index⟵1;18 if pcurr≠D then19 Extend vertically or horizontally from pcurr to D and condiser the points in N20 return N;


## 4. Demonstration of the Proposed Algorithm

An example has been shown in Figure3 to demonstrate the working of the proposed algorithm. Here in this example, the DQSS is to be fit in between S0,0 and D16,5. We find that the direction D1 is applicable for this example. The number of stairs or steps, Scount, is dy+1, i.e., 6. We find the possible values of k and m as 3 and 3. As, Slength is 16 here, we find that l1 and l2 can be set as 3 and 4, respectively, following the criteria: Slength≤k×l1+m×l2. Hence, we start path finding from S using n=0, s=1, l1=3, and l2=4. As shown in the procedure of Algorithm 1, pcurr is the current point during path making. We extend from the current point using nonsingular code’s run lengths as applicable. Stairs are created using the jumps because of the application of the singular code, and we gradually proceed towards the destination point D. If the current point pcurr reaches either the row (when pcurr.y=D.y) or the column (when pcurr.x=D.x) of the destination point in this process, we stretch horizontally or vertically towards D from that current point pcurr. An example has been shown in Figure 4. In this example, when pcurr reaches 18,13, the y values of pcurr and D become equal. Hence, we stretch from 18,13 to 20,13.Figure 3
Demonstration of working of the algorithm; DQSS direction isD1, n=0, s=1, and l1,l2=3,4; green nodes: active, gray nodes: sleeping, and red nodes: dead (the path does not go through any dead node).Figure 4
Demonstration of working of the algorithm.n=1, s=0, l1=3, and l2=4.


## 5. The Protocol Using DQSS

Our proposed method works on a regular rectangular grid [38], where sensor nodes are positioned at grid intersection points. Our objective is to find the shortest quasistraight line path from the sender to the receiver. Sensor nodes are classified as given below:
(i)
Active nodes: the nodes which are active in data transmissions(ii)
Sleeping nodes: initially, the nodes are sleeping and become activated based on requests(iii)
Dead nodes: dead nodes do not work in any condition as they are not in working condition; the dead nodes may be replaced with sleeping nodesWireless sensor nodes may be fixed nodes or mobile nodes. But in our case, we assume that the mobility of nodes is very less, and during movement, the nodes communicate with a core positioned at the grid points. So, virtually, the grid points are always the sensor nodes’ locations. If a node is not active but lying on the detected straight line, then either it is a sleeping node or a dead node. If it is a sleeping node, the state of the node is changed from sleeping to active. If it is a dead node, then it does not respond to path making requests, and it is avoided reaching the destination. It must be noted that a dead node can be avoided by updating the run length limits, i.e., by preponing or postponing the application of the singular code. It is true that because of this preponing or postponing of the singular code, some runs may have run lengths other thanl1 or l2. But, the length minimization constraint is maintained.


### 5.1. Sending and Receiving at Sensor Nodes

The starting point sensor initiates the path finding by sending a request to the prospective next sensor as per the codes and run lengths. We assume that the sensor nodes are equipped with local processors and storage registers to store their tagged information. If the next sensor responds to the previous, it is marked into the path, and the process continues until the destination is reached. The information which are tagged with each sensor are primarily path ID, run ID, run limit, node ID,n, and s as shown in Table 3. Here, path ID is the ID of the connecting straight line path. We assume that a sensor node can be part of four paths at most. Every path has several runs of codes. These runs are differentiated as odd and even. The initial run ID is odd, followed by an even ID run, followed by an odd ID run, and so on. If the run ID is odd, the sensor node is part of a run with length equal to l1. If the run ID is even, the sensor node is part of a run with length equal to l2. Node ID denotes the index of the node within the run. For example, if node ID is i and run ID is odd, then the current sensor is i-th node of a run whose length is l1. Here, n and s are nonsingular and singular codes. All these pieces of information are stored and processed by the local processor. Using these values, we decide the next node at each sensor. For example, if the current node is l1-th node in an odd run, then the next prospective node in the straight line lies in direction s from the current point. The current point is the latest point decided to be in the straight line segment.Table 3
Information stored at each sensor node.
Path ID1,2,3,4Run IDodd/evenRun limitl1/l2Node IDin 1⋯l1 or 1⋯l2nsFor the DQSS example shown in Figure3, the triplet <RunID>,<RunLimit>,<NodeID> values (at sensor nodes) starting from the source node are as follows: odd,3,1, odd,3,2, odd,3,3, even,4,1, even,4,2, even,4,3, even,4,4, odd,3,1, odd,3,2, odd,3,3, even,4,1, even,4,2, even,4,3, even,4,4, odd,3,1, odd,3,2, and odd,3,3. Whenever a sensor node gets the node ID equal to run limit, it flips the run ID (odd to even or even to odd) and selects the next node in direction s from the current point.The decision-making process is very lightweight as no other arithmetic or complex computations are involved. The nodes check the index limits at every node and forward the incremented index information, whereas in Bresenham’s line drawing algorithm, we need to compute the decision parameter’s value at each pixel position to decide the next pixel [39]. In Bresenham’s algorithm, the decision parameter is updated by involving addition, multiplication, and comparison operations. In contrast, our method computes the necessary parameters once and only uses increment and comparison operations in the loop. Figure 5 shows a comparison of the DQSS line with the Bresenham’s line. Also, a comparison between DQSS and Bresenham’s line algorithm on the CPU times for various line segments is shown in Figure 6 and Table 4.Figure 5
Differences in line segments: DQSS and Bresenham’s line.Figure 6
CPU time: DQSS vs. Bresenham’s line (on18 different line segments as shown in Table 4).Table 4
Various line segments and the corresponding CPU time (in milliseconds).
L1:dx=10, dy=6L2:dx=20, dy=12L3:dx=30, dy=18DQSS2.6612.7662.801Bresenham2.9473.1023.158L4:dx=40, dy=24L5:dx=50, dy=30L6:dx=60, dy=36DQSS2.8332.8432.941Bresenham3.2503.2603.259L7:dx=70, dy=42L8:dx=80, dy=48L9:dx=90, dy=54DQSS2.9783.0143.038Bresenham3.2643.2803.321L10:dx=100, dy=60L11:dx=120, dy=72L12:dx=140, dy=84DQSS3.0393.0633.119Bresenham3.4063.4403.446L13:dx=160, dy=96L14:dx=180, dy=108L15:dx=200, dy=120DQSS3.133.2273.264Bresenham3.4663.5463.581L16:dx=250, dy=150L17:dx=300, dy=180L18:dx=500, dy=300DQSS3.2883.2883.409Bresenham3.6823.7483.939


### 5.2. Dead Node Avoidance

We assume that significantly fewer dead nodes will be present in the grid. During the making of the straight line path, at some point, if a dead node appears as the following selection, we wish to avoid it. This is done by increasing or decreasing the current nonsingular run length (run limit). We have the following two cases.(i)
The current nodepcurr is a dead node, and it is the first node of a run (reached using singular code s from the previous point). The run limit of the current run is increased by 1. An example is shown in Figure 7(ii)
The current nodepcurr is a dead node, and it is any node other than the first node of a run (reached using nonsingular code n from the previous point). The run limit of the current run is reset by index−1 (index points the current node pcurr. Hence, pcurr is avoided by applying a move using the singular code on the previous node of pcurr. An example is shown in Figure 8Figure 7
Dead node avoidance by increasing the current run length limit; the length of the first even run is increased by1.Figure 8
Dead node avoidance by decreasing the current run length limit; limit is reduced to 3 from 4.


### 5.3. Energy Consumption

In WSN, the energy consumed is the sum total of energy consumed by individual nodes (see Equation (1)) [40, 41]. Energy consumed by a node comprises of energy for transmitting packets (Et), that for receiving packets (Er), and consumptions because of sleeping (Es).
(1)ETotal=∑i=1nEi,where Ei=Et+Er+Es.ForEr and Es, most of the network simulators use standard values. However, Et depends on various factors. Most prominent of which includes packet size (l) and distance between nodes (d). Hence, Et may be expressed using the formula shown in
(2)Et=l∗Ebit+l∗λ∗d2,where λ is medium constant.Our proposed algorithm focuses on minimizing the path length between the two given nodes by finding a quasistraight line segment between the two nodes. Minimization of the path length ensures minimization of the energy consumption.


## 5.1. Sending and Receiving at Sensor Nodes

The starting point sensor initiates the path finding by sending a request to the prospective next sensor as per the codes and run lengths. We assume that the sensor nodes are equipped with local processors and storage registers to store their tagged information. If the next sensor responds to the previous, it is marked into the path, and the process continues until the destination is reached. The information which are tagged with each sensor are primarily path ID, run ID, run limit, node ID,n, and s as shown in Table 3. Here, path ID is the ID of the connecting straight line path. We assume that a sensor node can be part of four paths at most. Every path has several runs of codes. These runs are differentiated as odd and even. The initial run ID is odd, followed by an even ID run, followed by an odd ID run, and so on. If the run ID is odd, the sensor node is part of a run with length equal to l1. If the run ID is even, the sensor node is part of a run with length equal to l2. Node ID denotes the index of the node within the run. For example, if node ID is i and run ID is odd, then the current sensor is i-th node of a run whose length is l1. Here, n and s are nonsingular and singular codes. All these pieces of information are stored and processed by the local processor. Using these values, we decide the next node at each sensor. For example, if the current node is l1-th node in an odd run, then the next prospective node in the straight line lies in direction s from the current point. The current point is the latest point decided to be in the straight line segment.Table 3
Information stored at each sensor node.
Path ID1,2,3,4Run IDodd/evenRun limitl1/l2Node IDin 1⋯l1 or 1⋯l2nsFor the DQSS example shown in Figure3, the triplet <RunID>,<RunLimit>,<NodeID> values (at sensor nodes) starting from the source node are as follows: odd,3,1, odd,3,2, odd,3,3, even,4,1, even,4,2, even,4,3, even,4,4, odd,3,1, odd,3,2, odd,3,3, even,4,1, even,4,2, even,4,3, even,4,4, odd,3,1, odd,3,2, and odd,3,3. Whenever a sensor node gets the node ID equal to run limit, it flips the run ID (odd to even or even to odd) and selects the next node in direction s from the current point.The decision-making process is very lightweight as no other arithmetic or complex computations are involved. The nodes check the index limits at every node and forward the incremented index information, whereas in Bresenham’s line drawing algorithm, we need to compute the decision parameter’s value at each pixel position to decide the next pixel [39]. In Bresenham’s algorithm, the decision parameter is updated by involving addition, multiplication, and comparison operations. In contrast, our method computes the necessary parameters once and only uses increment and comparison operations in the loop. Figure 5 shows a comparison of the DQSS line with the Bresenham’s line. Also, a comparison between DQSS and Bresenham’s line algorithm on the CPU times for various line segments is shown in Figure 6 and Table 4.Figure 5
Differences in line segments: DQSS and Bresenham’s line.Figure 6
CPU time: DQSS vs. Bresenham’s line (on18 different line segments as shown in Table 4).Table 4
Various line segments and the corresponding CPU time (in milliseconds).
L1:dx=10, dy=6L2:dx=20, dy=12L3:dx=30, dy=18DQSS2.6612.7662.801Bresenham2.9473.1023.158L4:dx=40, dy=24L5:dx=50, dy=30L6:dx=60, dy=36DQSS2.8332.8432.941Bresenham3.2503.2603.259L7:dx=70, dy=42L8:dx=80, dy=48L9:dx=90, dy=54DQSS2.9783.0143.038Bresenham3.2643.2803.321L10:dx=100, dy=60L11:dx=120, dy=72L12:dx=140, dy=84DQSS3.0393.0633.119Bresenham3.4063.4403.446L13:dx=160, dy=96L14:dx=180, dy=108L15:dx=200, dy=120DQSS3.133.2273.264Bresenham3.4663.5463.581L16:dx=250, dy=150L17:dx=300, dy=180L18:dx=500, dy=300DQSS3.2883.2883.409Bresenham3.6823.7483.939


## 5.2. Dead Node Avoidance

We assume that significantly fewer dead nodes will be present in the grid. During the making of the straight line path, at some point, if a dead node appears as the following selection, we wish to avoid it. This is done by increasing or decreasing the current nonsingular run length (run limit). We have the following two cases.(i)
The current nodepcurr is a dead node, and it is the first node of a run (reached using singular code s from the previous point). The run limit of the current run is increased by 1. An example is shown in Figure 7(ii)
The current nodepcurr is a dead node, and it is any node other than the first node of a run (reached using nonsingular code n from the previous point). The run limit of the current run is reset by index−1 (index points the current node pcurr. Hence, pcurr is avoided by applying a move using the singular code on the previous node of pcurr. An example is shown in Figure 8Figure 7
Dead node avoidance by increasing the current run length limit; the length of the first even run is increased by1.Figure 8
Dead node avoidance by decreasing the current run length limit; limit is reduced to 3 from 4.


## 5.3. Energy Consumption

In WSN, the energy consumed is the sum total of energy consumed by individual nodes (see Equation (1)) [40, 41]. Energy consumed by a node comprises of energy for transmitting packets (Et), that for receiving packets (Er), and consumptions because of sleeping (Es).
(1)ETotal=∑i=1nEi,where Ei=Et+Er+Es.ForEr and Es, most of the network simulators use standard values. However, Et depends on various factors. Most prominent of which includes packet size (l) and distance between nodes (d). Hence, Et may be expressed using the formula shown in
(2)Et=l∗Ebit+l∗λ∗d2,where λ is medium constant.Our proposed algorithm focuses on minimizing the path length between the two given nodes by finding a quasistraight line segment between the two nodes. Minimization of the path length ensures minimization of the energy consumption.


## 6. Conclusion

This paper proposes a novel quasistraight line routing protocol based on quasistraight line fitting, which is derived from Freeman’s chain code-based straightness properties. The proposed algorithm focuses on the grid-based deployment of sensor nodes in WSN. If the constructed path attempts to go through a dead node, the path is modified so that the length minimization constraint is maintained with minimum deviation. The method has been compared with a standard straight line finding algorithm, and the results show its applicability.



---

*Source: 8425506-2022-05-11.xml*