Document Type : Research Paper
Authors
1 Computer Engineering Department, Science and Research branch, Islamic Azad University, Tehran, Iran
2 Department of Mathematics and Computer Science, Shahed University, Tehran, Iran
3 Computer Engineering Department, Science and Research Branch, Islamic Azad University, Tehran, Iran
Abstract
Keywords
Recent advances in technology have triggered the development of low-cost, low energy and multipurpose sensors. These nodes are autonomous devices that are capable of receiving, processing and integrated communication [1]. When a large number of sensors collaborate in monitoring a vast physical environment, they form a wireless sensor network [2]. Wireless Sensor Networks (WSNs) are used in a variety of fields such as environmental monitoring, military observations, etc. [3].
Geographic routing [4] is considered as an efficient routing protocol that is simple and scalable for WSNs. In this routing, the source node sends data packet to its neighboring node within one hop, which is geographically the nearest node to the destination node. This process is reiterated until the destination node receives the data packet. Geographic routing requires the following three basic conditions:
Condition no. 1 can be obtained by sensor node locating and condition no. 2 can be fulfilled through the exchange of messages. For condition no. 3, the available geographic routing protocols entirely assume that source nodes can obtain the location of the destination node through some positioning services. How the source node can achieve the target position will not be discussed here in detail. Consequently, finding affordable methods to derive the location of the destination node in a sensor network has become a research topic that is termed "the sink locating". Determining the location of the destination node is one of the key techniques in geographic routing in WSNs. Sink Locating algorithms have been classified into the following two groups:
1. Flooding-based
2. Quorum-based
In flooding-based algorithms, the destination node in the network periodically sends its positioning information. These methods are divided into two categories: global and local. The destination node in the global approach sends its positioning information to all nodes in the network whereas in local approach, it sends the information to a limited area of the network.
In quorum-based algorithms, a destination node sends a message, called Sink Location Announcement (SLA), including positioning information to a set of nodes. A source node sends a message, called Sink Location Query (SLQ), to a set of nodes. Node that receives both messages responses destination information to the source. Quorum-based algorithms can be divided into two categories of hierarchical and flat algorithms. In the first category, a hierarchical structure exists between the quorums while no such structure exists in the second category. In this paper, using the fano plane as one of the structures of combinatorial schemes, a solution is presented to the problem of sink locating. In this algorithm, Fano Plane is created using sensors and a compound plane is obtained where both paths intersect. Source and target sensors send their messages along compound fano plane paths and sensor that is located in the intersection, announces the location of the destination sensor to the source sensor. The rest of this paper is structured as follows:
In the second part, the related works will be discussed. In the third part, the proposal will be elaborated along with the mathematical background of the concept. The fourth part is devoted to the evaluation of performance and comparison of proposals with parameters of paths crossing probability and the average length of message delivery paths. Finally, in the fifth part, a conclusion will be reached and presented.
This section involves elaboration of the proposed algorithms in the area of destination routing according to the categories mentioned in the introduction and described as sink locating.
A simple solution to get the target position for a source node is via flooding. In Flooding-based algorithms, a destination node periodically broadcasts position information across the network so that all nodes of the network can obtain the position of the destination node. These algorithms can be used in ad-hoc networks but they are not suitable for sensor networks since a great deal of network resources such as energy and bandwidth is occupied. Sensor network resources are far more limited than Ad-hoc network resources. In the rest of the paper, this algorithm will be referred to as Flooding.
To avoid overloading on global flooding-based algorithm, a local flooding-based scheme is provided based on a network structure that is called TTDD. In TTDD, a source node creates a global network structure to disperse information about its position while the destination node, locally broadcasts position information only to the size of a network cell. Thus, intersection points are caused between network structure and flood lines. In this method, despite the decrease in the range of the flooding, creating a global network structure will incur a lot of overhead.
In hierarchical algorithms, the network is divided into a large square networks. A node inside each square network is chosen as the locating server. These locating servers are called the level one server. Among these locating servers of level one, a number of nodes are selected as level two locating servers. Each level two locating server manages multiple servers of level one. Then, among level two locating servers, a number of nodes are selected as level three. This process continues until one or more locating servers of level n are selected.
If a node needs to obtain the location of the destination node, first it asks from the nearest locating server level one. If sink location is not found, then it asks from the nearest locating server level two. This process continues until sink location is found. The algorithm presented in [8] is hierarchical.
This algorithm yields good performance in ad-hoc networks while it is not suitable for sensor networks with low capacity and limited energy. The higher the server level, the heavier the damage that is incurred from overload. A higher level locating server needs higher memory space and higher processing capacity.
Fig. 1. The algorithm presented in [9].
In addition, the loss of higher level server may cause failure in location service in a large area. Moreover, updating location creates a large overhead for multiple locating servers. The other issue is that, this algorithm is based on the assumption that the network is on a regular basis (like a square region) but in practice, a network can be temporarily in an irregular shape. As a result, available hierarchical locating services are not suitable for irregular sensor networks.
Algorithms presented in [9, 10, 11] are of flat type. At first, these algorithms identify network border and select a number of border nodes as anchor nodes. Then, they divide border nodes into four categories (North-South-East-West). As soon as occurrence of an event, one sensor node turns into a source node. For example, node E in Fig.1 is the source node.
The source node E, sends one SLQ message to the desired anchor nodes of M and N using geographic routing respectively in Sections 1 and 3 and, thus, produces one SLQ path.
All sensor nodes that sniff SLQ packet during the query, store the information in their source list table. When there is a destination in sensor network, that destination sends SLA message using geographic routing to two desired anchor node P and Q in sections 2 and 4 respectively. All nodes that sniff SLA packet along its path store sink location in their sink locating table.
SLQ path and SLA path have at least one common point (intersection). Sensor nodes near the intersection which sniffed both SLQ and SLA packets, try to get the source location and destination location and send a SLR (Sink Location Reply message) packet to source node using geographic routing. After discovering the original location, the source node starts to send data packets to the original destination by geographic routing. This algorithm is called QSLS.
Fig. 2. Fano Plane.
The proposed locating algorithm is created based on combinatorial scheme, points and lines in Fano plane. Combinatorial scheme is used in various fields of computer science, including coding theory and cryptography. In this research, the use of Fano plane in sink locating problem is discussed. Since the Fano plane is a sort of finite geometry, it is described firstly. To define finite geometry, combinatorial scheme is initially described. Combinatorial scheme includes a set of domain X and a set of B, usually as a subset of that domain similar to the way in which the edges of a simple graph can be shown as pairs of vertices.
Block scheme is a kind of combinatorial scheme. A block scheme of B has a non-empty domain and a non-empty set of subsets of X that is called the block.
Balanced Incomplete Block scheme (BIBD) is one of the block schemes that Consists of layout v separate object, in b blocks so that each block contains exactly k distinct object, any object exactly r different blocks exist and each pair of distinct objects appear exactly λ blocks. This scheme is displayed with or where there is a relationship between and .
If is called symmetric BIBD and therefore . Different types of combinatorial schemes on a finite set of elements are called finite geometry.
A Fano plane P, is a BIBD with parameters in which there are seven points and seven lines. Each line is composed of three points and both lines are at a point of intersection. Fano plane is shown in Fig. 2. A Fano plane is a type of finite geometry and thus, is a type of combinatorial schemes.
Table1.The proposed locating algorithm
|
1.1. Per seven points, a Fano plane, is created 1.2. Repeat steps 2-1 up to number
3.1. Fano pages are connected to each other
|
In this scheme, it is assumed that there is a sensor network with N nodes in the environment. In this network, sensor nodes are static while the destination node is dynamic. Each node can obtain its own location information using the Global Positioning System (GPS) [12] or other locating services.
The main idea of this project is to create SLQ and SLA paths using Fano plane and since in Fano plane both lines intersect, the challenge of the intersection of two paths is solved. The proposed algorithm is described below.
First, the number of Fano planes is to be calculated. Since each Fano plane is composed of seven points, the number of Fano plane is calculated using formula . In the second step, the formation of Fano planes will be discussed. That is, a Fano plane is formed for every seven sensor. This step continues for maximum n times.
Finally, as the last step, a compound page from connection of Fano planes is formed. The proposed algorithm is described in Table 1.
The proposed algorithm is shown in Fig. 3.
To obtain the target position, the source node sends a SLA message and the destination node sends a SLQ message to the nearest page plane and after passing through a block of a page, it enters the second page and goes through all pages which are connected. These blocks create SQL and SLA paths, respectively. These two paths have a point of intersection and the intersection node sends the location of the destination node to the source node using the Sink Location Reply message (SLR).
Fig. 3. Proposed algorithm
Theorem 1: Both of the SLQ and SLA paths are cross.
Proof: As mentioned in the definition of Fano plane, both lines on this page have exactly a point of intersection. SLQ and SLA paths are equivalent to the Fano plane lines and As a result, their intersection is guaranteed.
The evaluation of the proposed solution was conducted by simulation tool NS-2 [13]. For similar tasks in the field, the criterion of "total transmission" was used to evaluate the algorithms. This evaluation criterion is defined as the delivery of the entire SLA, SLQ and SLR messages for once discovered destination location. This criterion is according to total length of the message path. In this paper, the efficiency of the proposed algorithm is compared to the QSLS and Flooding algorithms by simulation using network simulator NS-2. To ensure the assessment results, the simulation was executed for five times. In each run, 30 sensor nodes, with different positions were used. Each source and destination nodes, SLA and SLQ process is done only once during each run.
Three studies are examined in this subsection. In the first study, a source node and the destination is considered. In the second study, the effect of destination node number on total number of transfer has been studied and finally, the effect of changing the number of source nodes is evaluated. In this paper, the total transmission is evaluated as the number of hops.
Fig. 4. the total number of transmissions (number of Hops) in case of a source and sink
Fig. 5. the total number of transmissions (number of Hops) in case a source and several sink
In Fig. 4, the total number of transmissions in each time discovering location of target, in case "a source and destination node" in the network is shown. In each run, to discover location of the target, a different source and destination nodes is considered.
The total number of transfers in Flooding method is more than the rest of the methods because all nodes participate in this method. Overhead in Flooding is less than QSLS method because SLA and SLQ messages are sent during direct paths and all nodes do not participate in the delivery of these messages.
The proposed algorithm for sending SLA and SLQ messages uses the blocks with fixed hops while QSLS method of geographic routing uses a different number of hop. Thus, the number of hops in QSLS method is more than the proposed algorithm.
In Fig. 5, the total number of transmissions for SLA and SLA, in “A source and multiple destination nodes” in the network is shown.
Fig. 6. the total number of transmissions (number of Hops) in case a sink and several sources
A source node and the number of two up to five for the destination node are considered. According to the figure, in flooding method, since each destination node broadcasts its position across the network, by increasing of destination node, the total number of transmissions increases.
Fig. 6 shows the total number of transfer algorithms based on a destination and several sources for two to five nodes.
According to this figure, the total number of transmissions in proposed algorithm under the same conditions is less than QSLS method. The total number of transmissions in Flooding method changed a little because the source nodes earn the target position by broadcast and do not need to sink location query (SLQ).
By combining the simulation results, we can conclude that the total number of transmissions in proposed algorithm is lower than that of the Flooding and QSLS method.
In this paper, we suggested a destination location algorithm based on Fano plane. In fact, we proposed a new aspect to the locating from the perspective of combinatorial design. The challenge of this research ensures intersection of SLA and SQL paths in at least one point and the proposed solution ensures this intersection. The proposed solution is evaluated using simulation tool NS2. The evaluation results revealed that the proposed solution is more efficient than the existing solutions.
)