TECHNICAL FIELD
The present disclosure relate to the field of wireless sensor network. More particularly  embodiments of the disclosure relate to a method and system for designing a multi-hop wireless sensor network with minimum number of relay nodes  while meeting quality of service requirements and connectivity.
BACKGROUND
A wireless sensor network consists of many low-cost  low-power sensor nodes  which performs sensing  simple computation  and transmission of sensed information. The sensor nodes have limited communication range. Large area networks therefore require multi-hop communication. Relay nodes are deployed in the network to get reliable communication links across the network. The problem with the existing designing techniques of a network for predefined sensors is with the placement of the relay nodes so as to meet desired quality of service requirements and the connectivity requirements in the wireless sensor network.

Our objective of designing a network is to obtain an initial set of relay locations and paths based on a propagation model and a theoretical delay model. The network design should be such that the delay constraint on the system is met  while also ensuring high delivery probability  and the number of relays kept to a minimum to minimize costs. But when the network obtained in the design phase is deployed on field  some links may not behave as predicted by the model  and therefore the network may fail to meet the desired quality of service requirements on the field.

The conventional methods address the problems of designing an efficient network based on modeling and simulation. The relay nodes are deployed based on a model without actual input from the deployed nodes. The position of the sensors and relays are determined by modeling the real world environment using simulators which can accurately predict its behavior. The design plan includes the stages of modeling  proposing locations for node placement and analysis. The analysis involves generating predicted results of deployment and connectivity. Any modifications to the design are made by the user based on these analysis results. The conventional methods also provide a tool which performs the process of network deployment  initialization  simulation  and performance evaluation and optimization. The network deployment phase is to find an optimal placement solution. The initialization phase involves setting of wireless communication parameters  environment information  Media Access Control (MAC) protocol model etc. The simulation phase is to do an analysis of the wireless sensor network deployment and the evaluation and optimization phase evaluates the simulated virtual wireless sensor network.

The performance evaluation and optimization in the above mentioned tools are only through modelling and simulation. There is no actual measurement and evaluation of link quality before the full deployment of the network. Most of the related work involves using a model for communication range prediction and an algorithm for relay placement. The relay placement is only evaluated by using simulation tools which require a lot of details about the barriers and obstacles in the environment. The deployment process does not factor into it  the unpredictability of the wireless links which require on-field testing of modelled links before actual deployment.
There are also products that deploy relays for sensor connectivity based only on on-field measurement and evaluations. They perform actual on-field link quality measurement and evaluation  but the node placement strategy is not algorithm based. Any broken links are corrected and tested only based on the intuitive prediction of the deployment engineer.
In the first few methods mentioned  network design was mostly modeling and simulation based with no design verification or repair based on actual measurement and evaluations. In the later methods mentioned the network design was only measurement and evaluation based with no initial deployment approach. The drawbacks of these methods are that they focus mostly on modeling and simulations or completely ignore modeling and design based only on measurement and evaluations. Repair of the network deployed based on modeling results by actual link quality measurement and evaluations do not feature in any of these deployment methodologies. Further  they are not concerned with aspects like MAC mechanisms  and associated hidden and exposed node problems  to name a few  which can drastically degrade the performance of the network. They also do not consider quality of service requirements of the network essential to industrial sensor networks which are very sensitive to delay of the information being relayed to the control center.
Hence a delay constrained or quality of service aware relay placement method that adheres to delay constraints and ensures high delivery probability while trying to optimize relay nodes count is needed. Further  there also exists a need for providing actual measurement and evaluations of link quality of the network after prediction of relay nodes’ locations  based on which the network is repaired by adding more relay nodes till the required conditions of quality of service and connectivity are met.
SUMMARY OF THE DISCLOSURE

The shortcomings of the prior art are overcome and additional advantages are provided through the provision of method and system of the present disclosure.
The present disclosure solves limitations of existing techniques by designing a multi-hop wireless network for interconnecting sensor nodes at a given location to a base station at a given location with minimum number of relay nodes while meeting quality of service requirements and connectivity.
In one embodiment  the present disclosure validates the wireless sensor network for predefined requirements of quality of service and connectivity.

In one embodiment  the present disclosure performs an iterative process of deploying the network and measuring link quality of each link in the network and evaluating the network until the network meets predefined requirements of quality of service and connectivity.
In one embodiment  the present disclosure provides an energy efficient network by restricting the number of paths using any particular node  thereby restricting the energy drain at any particular node.
Additional features and advantages are realized through the techniques of the present disclosure. Other embodiments and aspects of the disclosure are described in detail herein and are considered a part of the claimed disclosure.
In one embodiment  the present disclosure provides a method for designing a multi-hop wireless network for interconnecting sensor nodes at given locations to a base-station at a given location.   The method comprises proposing location for placing one or more relay nodes based on a model for radio links in a deployment environment and for predefined requirements of quality of service and connectivity of a network. The one or more relay nodes are placed in the proposed locations  thereby creating an initial deployment of the network. After placing the relay nodes in the proposed locations  quality of each link in the deployed network is measured for the predefined requirements. The link is a connection between a sensor node and a relay node  or a sensor node and the base-station  or two relay nodes  or a relay node and the base station. Then the network consisting of the measured links between the deployed relays nodes along with the sensor nodes is evaluated to determine if it meets the predefined requirements of the quality of service and connectivity between the sensor nodes and the base-station. If the evaluated network does not meet the predefined requirements of the quality of service and connectivity  then more relay nodes are augmented in the network. The process of proposing the location for the relay nodes  measuring the link quality of each link in the network  and evaluating the network for the predefined requirements of quality of service and connectivity is repeated until the requirements are met. When the network meets the predefined requirements of quality of service and connectivity  the network is operated in the deployment environment.
The design process assumes uniform transmit power level at all the nodes in the network  this can be optimized on once the design is compete. A power optimization method runs on the nodes in the network to find the least power level each node can transmit at so that connectivity and quality of service are still maintained.
In one embodiment  the present disclosure provides a system for designing a multi-hop wireless network for interconnecting sensor nodes at given locations to a base-station at a given location  wherein the sensor nodes can also serve as radio relays. The system comprises a relay placement module  a measurement and evaluation module  and an augmentation module. The relay placement module proposes location for placement of one or more relay nodes and routes between sensors and the base-station based on a model for radio links in a deployment environment and predefined requirements of quality of service and connectivity. The model for feasible radio links is the maximum length of such a link. The one or more relay nodes are placed in the proposed locations. Upon placing the one or more relay nodes  the evaluation module evaluates link quality of each link in the deployed network for the predefined link quality requirements and then evaluated the network consisting of these links for quality of service and connectivity. The augmentation module augments one or more relay nodes if the evaluated network does not meet the predefined requirements of quality of service and connectivity.
The foregoing summary is illustrative only and is not intended to be in any way limiting. In addition to the illustrative aspects  embodiments  and features described above  further aspects  embodiments  and features will become apparent by reference to the drawings and the following detailed description.
BRIEF DESCRIPTION OF THE DRAWINGS
The novel features and characteristic of the disclosure are set forth in the appended claims. The embodiments of the disclosure itself  however  as well as a preferred mode of use  further objectives and advantages thereof  will best be understood by reference to the following detailed description of an illustrative embodiment when read in conjunction with the accompanying drawings. One or more embodiments are now described  by way of example only  with reference to the accompanying drawings.
Fig.1 is an exemplary block diagram which illustrates system architecture for designing a network for sensors.

Fig.2 shows flow chart illustrating the process of designing a network for sensors.

Fig.3 shows flow chart illustrating power optimization method used to set transmit power level at nodes after the network is designed.

Fig.4 shows flowchart illustrating trace route process at base station.

Fig.5 shows flow chart illustrating trace route process at nodes in a network.

The figures depict embodiments of the disclosure for purposes of illustration only. One skilled in the art will readily recognize from the following description that alternative embodiments of the structures and methods illustrated herein may be employed without departing from the principles of the disclosure described herein.

DETAILED DESCRIPTION
The foregoing has outlined rather broadly the features and technical advantages of the present disclosure in order that the detailed description of the disclosure that follows may be better understood. Additional features and advantages of the disclosure will be described hereinafter which form the subject of the claims of the disclosure. The novel features which are believed to be characteristic of the disclosure  both as to its organization and method of operation  together with further objects and advantages will be better understood from the following description when considered in connection with the accompanying figures. It is to be expressly understood  however  that each of the figures is provided for the purpose of illustration and description only and is not intended as a definition of the limits of the present disclosure.
An embodiment of the present disclosure provides a method and system for designing a multi-hop wireless network for interconnecting sensor nodes at given locations to a base-station at a given location  wherein the sensor nodes can also serve as radio relays.

A sensor network is a network composed of a large number of sensor nodes and a base station to receive information from the sensors. The sensor nodes are small and inexpensive  so that they can be produced and deployed in large numbers  and hence their resources in terms of energy  memory  computational speed and bandwidth are severely constrained. There are different sensors such as pressure  accelerometer  camera  thermal  microphone  etc. They monitor conditions at different locations  such as temperature  humidity  vehicular movement  lightning condition  pressure  soil makeup  noise levels  the presence or absence of predefined objects  mechanical stress levels on attached objects  the current characteristics such as speed  direction and size of an object.

The sensor nodes communicate sensor data to a base station at regular intervals of time. Long distance transmission by sensor nodes is not energy efficient  as energy consumption of the sensor nodes is a superlinear function of the transmission distance  and therefore  the relay nodes are used. The relay nodes should be placed in the network in such a way that the network meets predefined requirements of quality of service and connectivity.

Fig.1 is an exemplary block diagram which illustrates system architecture for designing a network for sensors.

The system (100) comprises a relay placement module (101)  a measurement and evaluation module (103)  a validation module (105)  augmentation module (107)  power management module (113) and a path management module (111). The relay placement module (101) proposes locations for the placement of one or more relay nodes and routes between the sensors and the base-station in a deployment area. The relay placement module proposes the locations based on a model (109) for links in the deployment environment (109). The relay placement module (101) takes the model (109) as input from the user through a GUI. The model (109) for feasible radio links includes but not limited to the maximum length of such a link. The network is deployed in a deployment area by placing the one or more relay nodes in the location proposed by the relay placement module (101). The network is evaluated by the evaluation module (103)  for predefined quality of service requirements and connectivity after measuring the quality of each link in the network. A link is said to exist  or is considered to be a good link if the measured link quality meets predefined quality requirements and is a bidirectional link. The links are between a sensor node and a relay node  or a sensor node and the base-station  or two relay nodes  or a relay node and the base station. The predefined link quality requirement includes  but not limited to  packet error rate on a link. The predefined requirements of the quality of service are transmitting data packets from the sensor node to the base station within predefined time. The predefined requirements of the connectivity are providing multi-hop paths from each sensor node to the base station such that each path meets the delay constraint while ensuring high delivery probability  and providing multiple node disjoint multi-hop paths from each sensor node to the base station such that each path meets the delay constraint while ensuring high delivery probability.
The augmentation module (107) performs augmentation of one or more relay nodes in the network when the evaluated network’s quality of service and/or connectivity does not meet the predefined requirements of quality of service and connectivity. The location for augmenting one or more relay nodes is provided by the relay placement module. The validation module (105) measures for each sensor node the average time delay of reception of data packets. It also measures the delivery probability of packets from each sensor node by measuring the number of dropped or delayed packets against the total number of packets sent. The power management module (113) provides an energy efficient network. The energy drain at any particular node is restricted by restricting the number of paths using that particular node. This is done at the design phase. After the design phase the power optimization method described by Fig.3 is executed where the transmit power of each node is reduced till a level at which the network can still meet the quality of service and connectivity requirements. Finally for further reduction in energy drain. When a sensor node has multiple paths to the base station  the traffic from the sensor node is split across the paths so as to minimize the maximum energy drain at any node in the network. The path is a single-hop or multi-hop connection between a sensor node and the base station over which data is transmitted. The path management module (111) provides connectivity in the network by providing an alternate path for transmitting of data packets when one is not functional.
Fig.2 shows flow chart illustrating process of designing a network for sensors.

The objective of the initial design of the network is to obtain an initial set of relay node locations and paths based on a propagation model and a theoretical delay model such that the predefined requirements of quality of service and connectivity is met  and also the number of relay nodes is kept to a minimum to minimize costs. In one embodiment  the different phases of the design process are prediction  evaluation and augmentation.

At (201)  the relay placement module proposes locations for the placement of one or more relay nodes in a deployment environment based on a model for radio links. At 203  the one or more relay nodes are placed in the deployment area based on the proposed locations and thus the network is deployed in the deployment area. The location of the relay nodes should be such that the deployed network meets the predefined requirements of the quality of service and connectivity. The model (Fig.1) (109) is used as an input by the relay placement module for proposing the locations. In one embodiment  the relay placement module (101) proposes location for the placement of the relay nodes such that the number of relay nodes is minimizes and the delay in transmitting the data packets is bounded by a maximum delay. Also the relay placement module (101) provides multiple node disjoint paths from each sensor to the base station  with the predefined requirement of quality of service met along all of the designed paths. Such a design with path redundancy helps overcome node failures by providing an alternate path when one is not functional.

The prediction phase provides set of relay locations obtained from the relay placement module (101). A network implementer deploys the relay nodes in the locations obtained from the relay placement module. But  it is not guaranteed that the deployed network will perform according to design requirements. This is because the design is based on statistical models obtained from measurement and evaluations made in an environment similar to the one where the deployment is being planned  and hence can only approximate the actual situation on the predefined area. In reality  the behavior of the network is very complex and unpredictable. Hence the links proposed by the relay placement module need to be actually tested out in the deployment environment..

At (205) link quality between each pair of the deployed nodes is evaluated. A link is said to exist  or is considered to be a good link if it meets certain pre-defined design requirements and is a bi-directional link. The process of evaluation is described below.

Firstly  the relay nodes are deployed in proposed locations. The base station maintains a list of all the deployed nodes that has to participate in the process for evaluating the link quality. The base station sends a command to start the evaluation process to any relay node from the list. The relay node receives the command and responds with an acknowledgment. If the relay node does not respond with an acknowledgment within predefined time  then the base station moves to the next relay node. On receiving the command  the relay node broadcasts predefined number of data packets which are of the same length as that of the actual sensor packets. All the relay nodes receiving this relay node""s data packets will mark the link quality for the sending node in a table. The steps are repeated till all deployed nodes are participated. Upon the participation of all the nodes  the base station transmits a control command to all the nodes to stop updating the table. On receiving the command to stop updating the table  each node will send the table to the base station.

The link quality of each link given by the relay placement module is actually found after the process of evaluation. At this stage  a network graph of the actual links in the deployment area is obtained. At 207  the deployed network will be evaluated based on the measured link quality to check whether the deployed network meets the predefined connectivity and quality of service requirements. If the evaluation is successful  then the network design is complete and moves on to validating the network at 211 and operating the network at 213  but if the network graph obtained from the links in the deployment area does not meet the connectivity and quality of service requirements  then the network needs to be augmented with more relay nodes. The locations of the new relay nodes are given by the relay placement module. The locations of the new relay nodes will be based on the links proposed in the evaluation phase. At 209  the one or more relay nodes are augmented. The new links are then tested by the evaluation module and the process of proposing locations for the relay nodes  evaluation and augmentation is repeated until the network meets the predefined requirements of the quality of service and connectivity.

The design process is an iterative process involving proposing location of relay nodes and evaluation of the links in the predefined area  till the desired network is obtained. In one embodiment  after obtaining the desired network  the network is validated through analytical modeling and computer simulation to measure packet delivery probabilities of the network and to measure the traffic that the network can handle. Finally  the network is validated and tested in the predefined deployment area by collecting pseudo data packets from the sensor nodes and verifying the design requirements. After testing  the network enters the operational phase  where it begins to collect the sensor data and transmits the sensor data to the base station. The evaluation phase may be repeated at regular intervals of time  and network augmentation may be initiated if the requirements are not met.

In one embodiment  the analytical modeling technique is used for evaluating the performance of the network based on Carrier Sense Multiple Access with Collision Avoidance (CSMA/CA). CSMA/CA is a protocol for carrier transmission in wireless local area networks. The network comprises sensor nodes  which generate sensor data packets  and relay nodes which only forward packets. A detailed stochastic process at each node is considered  and analyzed the process by taking into account the interaction with neighboring nodes via certain unknown variables (e.g.  channel sensing rates  collision probabilities  etc.). By coupling this analysis of the various nodes  fixed point equations are obtained that can be solved numerically to obtain the unknown variables  thereby yielding approximations of time average performance measures  such as packet discard probabilities and average queuing delays. Using these parameters  the quality of service of the network is measured. After performing the analytical modeling technique  the network is validated against simulations.

In one embodiment  the network design after being modeled analytically is verified using a network simulator. The network simulator simulates traffic on the designed network and verifies the predefined network parameters. The analytical modeling technique and computer simulation phases provide the frequency of traffic that the designed network can handle and also provide the delivery probabilities that can be obtained.

In one embodiment upon completion of the validation process  the network is tested in the deployment area for quality of service constraints and connectivity. This phase of testing is performed by initiating pseudo traffic from the source nodes. Data packets of the same size as the actual sensor data are sent as pseudo traffic. On sending a command for generating traffic  each source node sends pseudo sensor data packets. Data packets collected at the base station over a long period of time  packet drop ratio and delayed packet ratio statistics are measured. A log of per-packet delay of the received packets is maintained. This data is used to check whether the designed network meets the specified quality of service requirements.

In one embodiment  upon the design and the validation phases  the deployment process is completed and the network is made operational. In the operational stage  the time duration  which is of the order of milliseconds  required to receive data from each sensor node depends on the number of hops it is away from the base station. A time frame is created with one slot allocated to each sensor node. Each sensor node sends in its time slot  ensuring a lone packet in the network at a given time instance. This operation requires time synchronization among the nodes in the network for which a FTSP (flooding time synchronization protocol) is implemented. The lone packet model which is being used in the design can be pushed to handle a traffic level of a few packets every few seconds based on the analytical modeling which is adequate for condition monitoring applications.

Once the network is designed a power optimization method is employed to set the transmission power level of all the nodes in the network. Fig.3 shows the flowchart illustrating the process of power optimization. To begin with (301) the transmit power level of the nodes in the network is set to a constant level provided by the user. This is reduced by one step from what it was designed for  and link quality is measured. (303) The link quality of the measured links is checked to see if any of the links that are part of the network (part of any of the multi-hop paths from any of the sensor nodes to the base station)  now have link quality less than the predefined minimum  set to ensure connectivity and quality of service with high delivery probabilities. If yes  then (309) the nodes which have links of link quality less than the predefined minimum are identified  and the power level of those nodes are set to the transmit power level of the previous iteration. The transmit power level of the nodes is then reduced by another level and link learning is done again. This is repeated until the power level of all the nodes in the network is set (311) or the least power level possible is reached (305)

If the designed network has path redundancy  a mechanism is needed to distribute the traffic between the paths and monitor node failures. A trace route algorithm is implemented for distributing the traffic between the paths and monitor node failures.

Fig.4 shows flowchart illustrating trace route process at the base station. Base station has a list of all the sensor nodes in the network and initiated the process of sending trace route packets to the sensor nodes  one at a time. At 401  the base station selects the source to which trace route packets are to be sent. At 403  the base station selects a path for sending trace route packets for a particular sensor node. Each sensor node may have multiple paths to the base station. In one embodiment  the base station selects the path based on round-robin scheduling algorithm. At 405  the base station sends the trace route packets through the selected path and waits for acknowledgment from the immediate next hop node along that path. At 407  the base station checks if this acknowledgment is received. If the acknowledgment is received  the process stops and if the acknowledgment is not received then the base station will choose the next path of the particular source for sending trace route packets. The trace route packet sent by the base station is forwarded by the relays in the path with an acknowledgment being requested at each hop. If an acknowledgment is not received at any hop  a path broken packet is generated and sent back to the base station to alert it of the broken link.

Fig.5 shows flow chart illustrating trace route process as seen by the nodes in the network. At 501  the process starts and at 503 the nodes wait for the trace route packets from the base station. At 505  the node checks for the trace route packets. If the nodes receive the trace route packets then it moves to 507. If the node does not receive the trace route packets then the nodes will wait for the trace route packets from the base station. At 507  when a trace route packet is received  the node ID of the node that received it is checked against the sensor node ID that it was intended for. If the node ID is same as the source ID then the sensor node that received it will use the path  through which the trace route packets were sent to it  for routing data packets. If the node ID is not same as the source ID then the trace route packet will be forwarded to next hop in the network at 511. At 513  the relay node waits for the acknowledgment. If the relay node receives the acknowledgment then the process stops and if the acknowledgment is not received then at 515 a path broken packet is sent to the base station through the same path. The process described by Fig.4 and Fig.5 are repeated for each of the sensor nodes and the whole process of going through all the sensor nodes is repeated in a periodic manner  the time period of which is configurable.

Finally  the language used in the specification has been principally selected for readability and instructional purposes  and it may not have been selected to delineate or circumscribe the inventive subject matter. It is therefore intended that the scope of the invention be limited not by this detailed description  but rather by any claims that issue on an application based here on. Accordingly  the disclosure of the embodiments of the invention is intended to be illustrative  but not limiting  of the scope of the invention  which is set forth in the following claims.
With respect to the use of substantially any plural and/or singular terms herein  those having skill in the art can translate from the plural to the singular and/or from the singular to the plural as is appropriate to the context and/or application. The various singular/plural permutations may be expressly set forth herein for sake of clarity.
In addition  where features or aspects of the disclosure are described in terms of Markush groups  those skilled in the art will recognize that the disclosure is also thereby described in terms of any individual member or subgroup of members of the Markush group.
While various aspects and embodiments have been disclosed herein  other aspects and embodiments will be apparent to those skilled in the art. The various aspects and embodiments disclosed herein are for purposes of illustration and are not intended to be limiting  with the true scope and spirit being indicated by the following claims.

We claim:
1. A method for designing a multi-hop wireless network for interconnecting sensor nodes at predefined locations to a base-station at a predefined location  comprising:
a. proposing location of one or more relay nodes based on a model for radio links in a deployment environment for predefined quality of service and connectivity requirements of a network;
b. placing the relay nodes in the proposed locations  thereby creating initial deployment of the network;
c. measuring quality of each link in the deployed network for the predefined requirements of link quality  wherein each link is a connection between a sensor node and a relay node  or a sensor node and the base-station  or two relay nodes  or a relay node and the base station;
d. evaluating the deployed network  to determine whether the network meets the predefined requirements of quality of service and connectivity;
e. augmenting the network with one or more relay nodes when the evaluated network does not meet the predefined requirements of quality of service and connectivity;
f. repeating steps c  d and e until the network meets the predefined requirements of quality of service and connectivity.
2. The method as claimed in claim 1  wherein the sensor nodes serve as radio relays.
3. The method as claimed in claim 1  wherein the model for feasible radio links is maximum length of such a link.
4. The method as claimed in claim 1  wherein upon completion of step f  transmit power of each node in the network is reduced until the network still meets the predefined requirements of quality of service and connectivity.
5. The method as claimed in claim 1  wherein energy drain of each node is included in steps a  d  and e.
6. The method as claimed in claim 1  wherein the quality of service requirements and connectivity requirements are evaluated at intervals of time.
7. The method as claimed in claim 1  wherein the predefined requirements of the quality of service comprises receiving data packets from the sensor node at the base station within a predefined time and with a high delivery probability.
8. The method as claimed in claim 1  wherein the predefined requirements of the connectivity is providing reliable links along the path from each sensor node to the base station  and providing multiple paths from each sensor node to the base station to provide resilience against node failure.
9. The method as claimed in claim 1 further comprises validating the designed network by measuring the delay and delivery probability of data packets from each sensor node to the base station.
10. A system for designing a multi-hop wireless network for interconnecting sensor nodes at predefined locations to a base-station at a predefined location comprising:
a relay placement module configured to propose locations for placement of one or more relay nodes and routes between sensors and the base-station based on a model for radio links in a deployment environment and predefined requirements of quality of service and connectivity;
a measurement and evaluation module to evaluate link quality of each link in the deployed network for the predefined requirements of link quality  wherein each link is a connection between a sensor node and a relay node  or a sensor and the base-station  or two relay nodes  or a relay node and the base station; and then evaluate the network  using the measured links for predefined requirements of quality of service and connectivity; and
an augmentation module to propose the placement of one or more relay nodes when the evaluated network does not meet the predefined requirements of quality of service and connectivity.
11. The system as claimed in claim 10 includes an analytical evaluation model to study the designed network under various scenarios of traffic from the sensors.
12. The system as claimed in claim 10 further comprises power management module to provide an energy efficient network for sensors  by restricting number of paths using any particular node for data transmission  thereby restricting the energy drain of any particular node.