While a node in the active state, it periodically broadcasts its discovery message at Td intervals. A node in the discovery or active state can transit to sleep when it has determined that some other equivalent node will handle the routing function. When transiting to sleep, a node cancels all timers, sets the sleep timer and turns off its radio. A node in the sleeping state wakes up after an application dependent sleep time Ts.
In addition, simulations of GAF suggested that network lifetime increased proportionally to the node density. GAF incurs high packet loss rate, when a node that is actively routing packets is turned off.
A proposed solution is to inform the routing protocol of the possible state changes, so that traffic could be rerouted in advance. As nodes may move, the active node may leave its grid.
This may leave the prior grid without an active node to handle the routing. GAF suggests that each node to estimate the time it expects to leave its grid the expected node grid time and includes this information in the discovery message. When other nodes enter the sleep state, they could sleep for time value less than the estimated node grid time. GAF does not include any collision resolution scheme; if a node is placed on the boundary of two adjacent grids, it could overhear nodes belonging to two different grids.
A node signals when it detects high data loss, requesting additional nodes in the region to join the network in order to forward messages. A node may reduce its duty cycle if it detects high data losses due to collisions. A node also probes the network and does not join the routing infrastructure until it is "helpful" to do so. It uses adaptive techniques that permit the application to configure the underlying topology based on its needs while trying to conserve energy to extend network operational lifetime.
It also uses a self-configuring technique that reacts to the nodes operating conditions measured locally. Active nodes continuously stay awake and perform packet routing, while the rest of the nodes turn off their radio and go to sleep.
Sleeping nodes periodically check if they should become active and join the network topology. Initially, a node starts out in the test state. When in the test state, a node turns on its radio to exchange data and routing control messages.
It sets up a timer Tt and sends neighbor announcement messages. When timer Tt fires, the node enters the active state. If before timer Tt expires, the number of active neighbors is above the neighbor threshold NT or if the average data loss rate DL is higher than the average loss before entering the test state, the node moves into the passive state.
If multiple nodes make a transition to the test state, they use the node ID in the announcement message as a tie breaking mechanism higher IDs win.
The intuition behind the test state is to see if the addition of a new node can actually improve network connectivity. If before timer Tp expires, the number of neighbors is below NT and either DL is higher than the loss threshold LT or DL is below LT but the node received a help message from an active neighbor, it makes a transition to the test state.
This information is used by the active nodes to make an estimate of the total density of nodes in their neighborhood. Active nodes transmit their density estimate to any new passive node in the neighborhood. When timer Tp expires, the node turns its radio off and enters the sleep state. When a node goes to sleep, it sets up a timeout value Ts. When timer Ts expires, the node moves back to the passive state.
While in the passive state, nodes have their radio on and are able to overhear all packets transmitted by their active neighbors. No routing or data packets are forwarded in this state since this is a listen-only state. The intuition behind the passive state is to gather information regarding the state of the network without causing interference with the other nodes. Nodes in the passive and test states continuously update the number of active neighbors and the average DL values, which are measured locally.
Energy is still consumed in the passive state since the radio is still active. Finally, a node in the active state continues sending data and routing packets until it drains its battery.
When a node enters the active state, it never moves back into the test state. If the DL is greater than LT, the active node sends help messages to its neighbors, calling them to join the routing infrastructure. When using flooding as the routing strategy, the end-to-end delay is affected by the amount of randomization introduced at each hop and the number of nodes forwarding the packets. When density increases, the active case reduces the average per hop latency because there is a larger probability of a node picking a smaller random interval to forward the packet when there are more forwarding nodes.
ASCENT fixes the number of nodes able to forward packets independently of density and, consequently the average per hop latency tends to remain stable for the same randomization interval. ASCENT has the potential for significant reduction of packet loss rate and increases in energy savings as well as its mechanisms are responsive and stable under systematically varied conditions. Nodes do not consume energy equally or fairly. ASCENT may employ a load balance policy that allows nodes to switch state from time to time between active and non-active in order to ensure all nodes share the task of providing global connectivity equally and distribute the energy load.
In addition, it has too many parameters to be configured, which make it difficult to be optimized. SPAN Since even an idle receiver circuit can consume almost as much energy as an active transmitter [Chen et al. SPAN is a distributed, randomized power saving technique that conserves energy without significantly reducing the capacity or connectivity of the network.
SPAN algorithm builds on the notion that when a region of a shared channel wireless network has a sufficient density of nodes, only a reasonable number of them needs to be on at any time to forward traffic for active connections. Two of its neighbors cannot reach each other either directly or via one or two coordinators Non-Coordinator Coordinator Two of its neighbors cannot reach each other either directly Every pair of or via one or two neighbor nodes Every pair of its neighbors can reach each other coordinators can reach each either directly or via one or two other coordinators other via one or two other neighbors.
T is the round trip delay for a small packet over the wireless link. SPAN controls whether or not the radio is activated, rather than controlling the transmit power level. In addition to preserving connectivity, it also pays close attention to overall network capacity. SPAN adaptively elects coordinators from any nodes in the network. SPAN coordinators stay active continuously, and handle multi-hop packet routing within the ad hoc wireless network, while other nodes turn off their radios and move into power saving mode and periodically check if they should turn on their radios and join the forwarding backbone topology as a coordinator.
SPAN guarantees the following four properties are achieved. Firstly, enough coordinators are elected so that every node is in the radio range of at least one coordinator.
Thirdly, it minimizes the number of nodes elected as coordinators, thereby increasing network lifetime but without causing a significant loss of capacity or increase in latency.
Finally, SPAN elects coordinators using only information gathered locally in a distributed manner, where every node only consults its local routing table during the election process. A HELLO message is a tuple containing the node's status whether or not a node is a coordinator , its current coordinators, and its current neighbors. From these HELLO messages, each node builds a list of the node's neighbors and coordinators, and for each neighbor, a list of its neighbors and coordinators.
Non-coordinator nodes can periodically turn on their radios and listen or poll for their packets. SPAN leverages a feature of modern power-saving MAC layers, in which if a node has been asleep for a while, packets destined for it are not lost but are buffered at a neighbor [Chen et al.
When a node wakes up and turns on its radio, it can receive these packets from the buffering node, typically a coordinator. SPAN also requires a modification to the route lookup process at each node-at any time, only those entries in a node's routing table that correspond to currently active coordinators can be used as valid next-hops unless the next hop is the destination itself. Each node in the network periodically determines if it should become a coordinator or not.
The following coordinator eligibility rule in SPAN ensures enough coordinators are elected so that every node is in radio range of at least one coordinator. A non-coordinator node should become a coordinator if it discovers using only information gathered from local broadcast messages that two of its neighbors cannot communicate with each other either directly or via one or two coordinators. This election algorithm does not yield to a minimum number of coordinators required to merely maintain connectivity.
Announcement contention occurs when multiple nodes discover the lack of a coordinator at the same time. SPAN keeps the number of nodes which is elected as coordinators low, rotates this role being coordinator amongst all nodes, and resolves any contention by delaying a coordinator announcement with a randomized backoff delay. Each node delays announcing its willingness by a random time interval that takes two factors into account: a the amount of residual energy, and b number of nodes that will benefit from it being active.
At the end of the delay, the node re- evaluates its eligibility based on any newly received HELLO messages, and makes its announcement through a HELLO message, if and only if it still satisfies the eligibility rule. This combination ensures, with high probability, a capacity-preserving connected backbone at any point in time, where nodes tend to consume energy at about the same rate.
SPAN does all this using only local information, and consequently scales well. Each coordinator periodically checks if it should withdraw as a coordinator. A node should withdraw if every pair of its neighbors can communicate with each other either directly or via one or two other coordinators.
In order to also rotate the coordinators among all nodes fairly, after a node has been a coordinator for some period of time, it marks itself as a tentative coordinator if every pair of neighbor nods can communicate with each other via one or two other neighbors, even if those neighbors are not currently coordinators. A tentative coordinator can still be used to forward traffic. However, SPAN treats a tentative coordinator as a non-coordinator. Thus, by marking itself as tentative, a coordinator gives its neighbors a higher probability to become coordinators than itself.
SPAN's ability to save energy depends on three factors. Firstly, it depends on the node density, since the fraction of sleeping nodes depends on the number of nodes per radio coverage area. Secondly, the energy conservation also depends on a radio's power consumption in sleep mode and thirdly, the amount of time that sleeping nodes must be awake to listen for The simulation results of SPAN show that the network lifetime with SPAN is more than a factor of two better than without SPAN, for a range of node densities, without significant loss in the overall forwarding capacity.
Using SPAN on top of SPAN does not significantly increase packets delivery latency and number of hops each packet traverses, despite using fewer number of nodes to forward packets. The amount of energy that SPAN conserves increases only slightly as density increases.
As density increases, a smaller fraction of the nodes are elected coordinators, this is largely due to the fact that the current implementation of SPAN uses the power saving features of SPAN uses local broadcast messages to discover and react to changes in the network topology. SPAN integrates with SPAN never keeps a node awake unless it is absolutely essential for connecting two of its neighbors.
Furthermore, SPAN attempts to preserve the same overall system capacity as the underlying network where all nodes are awake, which ensures that no increase in congestion occurs.
The degree of mobility does not significantly affect routing with SPAN coordinators. SPAN not only preserves capacity, decreases latency, and provides significant energy savings. In addition to that, Nodes in SPAN decide to sleep or join the network based on connectivity information supplied by a routing protocol.
STEM: sparse topology and energy management Significant energy savings are only obtained by putting the node in sleep mode as long as possible, essentially disconnecting it from the network and changing the topology. STEM trades off energy consumption in the monitoring state refers to the state when sensor network is only monitoring its environment, waiting for an event to be detected and no data needs to be forwarded to the data sink versus latency of switching back to the transfer state refers to the state when the sensor network has data to forward , the result is a significant increase of network lifetime beyond any existing topology control schemes [Schurgers et al.
STEM places the sensor network in the monitoring state for vast majority of its lifetime. Ideally, they just turn on the sensors and some pre-processing circuitry.
When a possible event is detected, the main processor is activated to analyze the data in more detail. The radio, which is normally turned off, is only turned on if the processor decides that the information needs to be forwarded to the data sink.
However, in order to deliver data packets to the sink, there is another problem to overcome. The radio of the next hop in the path to the data sink may still be turned off, if it did not detect that same event.
As a solution, each node periodically turns on its radio for a short time to listen if others want to communicate with it. In fact, this can be viewed as the initiator node attempting to activate the link between itself and the target node. As soon as the target node receives this beacon, it responds to the initiator node, and both keep their radios on at this point.
If the packet needs to be relayed further, the target node will become the initiator node for the next hop, and the process is repeated. In order to avoid interference between the actual data transmission with the wakeup protocol, STEM uses dual radio to send them in different frequency bands. GAF divides the world where sensor nodes are deployed into small "virtual grids", where all nodes in a particular grid square are equivalent from the routing perspective.
GAF basically places one virtual active node in each grid to handle data routing, while the others are in the sleep mode. Alternatively, this results in a node lifetime increase of a factor 14!.
However, these benefits come at the cost of increased setup latency, which depends on the number of hops in the multi-hop path, and the specific applications in use, which controls how much latency is allowed, and consequently how much energy consumption can be reduced. Another disadvantage is when STEM and GAF combined together the routing protocol needs to address virtual nodes or grids instead of real nodes, which make the task more complicated. CBTC: cone-based topology control algorithm The Cone-Based Topology Control algorithm CBTC is a novel distributed cone-based topology control algorithm that increases network lifetime while maintaining global connectivity with a reasonable throughput in a multi-hop wireless ad hoc network.
Network operational lifetime is increased by determining per node minimal operational power requirement that guarantee the same maximum connected set of nodes as when all nodes transmit at full power [Wattenhofer et al.
In contrast to some previously proposed approaches in literature that rely on knowing and sharing the global coordinates information of the nodes in the network, the proposed algorithm is a distributed algorithm that relies solely on local information using directional information of incoming signals from neighboring nodes.. The CBTC algorithm is designed specifically for a static multihop wireless ad hoc networks deployed on a 2-dimensional surface.
It assumes that the radio communication unit is able to determine the direction of the sender by using double antennas when receiving a message, the environment is not obstructed, and nodes are homogeneous. The proposed algorithm consists of two phases, which are summarised as follows: Phase 1: Starting with a small radius, each node denoted by node u broadcasts a neighbor- discovery message. Each receiving node acknowledges this broadcast message.
Node u records all acknowledgments and the directions they came from. In this first phase, node u continues the neighbor discovering process by increasing its transmission power until either the above condition is met or the maximum transmission power P is reached. For smaller angles it can also guarantee good minimum power routes. Phase 2: In the second phase, the algorithm performs a redundant edge removal process without affecting the connectivity.
This phase is designed to reduce the node degrees, which helps in reducing interference but not guaranteed , collisions, and enhancing throughput.
Redundant edge removal is carried out without deteriorating the minimum power routes of the network. CBTC guarantees that the maximum connected set of nodes for the network will always be found.
The algorithm is computationally less demanding, and do not need to specify a region of deployment, which is an important consideration for the case when nodes regularly change deployment region due to mobility. Moreover, the algorithm does not need exact location information but only directional information, where nodes conclude information about their neighbors merely based on their relative signal strength and the signal arrival angle.
This can be a factor when cost of nodes is a consideration. The algorithm is not coupled with any radio propagation model. Due to the large influence of environment factor on radio frequency, communications radio propagation models can be notoriously inaccurate. Finally, the algorithm is able to give a worst-case analysis for both, the minimum power routes and the maximum nodes degrees in the network.
In [Li et al. They have also presented three optimizations to the basic algorithm — the shrink-back operation, asymmetric edge removal, and pairwise edge removal — and proved that they improve performance while still preserving connectivity. The algorithm extends easily to deal with reconfiguration and asynchrony. Most importantly simulation results showed that its very effective in reducing power demands.
One of the proposed algorithm disadvantages is its inability to detect or repair partitions; network partitions can occur when a swath of nodes are destroyed or obstructed. CBTC assumes that the nodes are deployed in a two-dimensional plane, which makes the algorithm unpractical for many applications.
It also requires additional hardware to determine the direction of signal. Surprisingly the XTC algorithm features all the relevant properties symmetry, connectivity, sparseness, and planarity of topology control while being faster than any previous proposals. The proposed topology control algorithm XTC works without assuming the exact node coordinates being known, and even in a mountainous and obstructed environment.
One of the foremost energy savings techniques is to abandon long-distance communication links and instead route a message over several small energy-efficient hops. The proposed algorithm consists of three main phases: Phase a: Neighbor ordering: each network node u computes a total order over all its neighbors in the network graph G. From an abstract point of view, this order is intended to reflect the quality of the links to the neighbors.
A node u will consider its neighbors in G in the third step of the algorithm according to neighbor order with respect to decreasing link quality. The link to a neighbor appearing early in the order is regarded as being of higher quality than the link to a later neighbor.
They assumed that the neighbor order corresponds to the order of the neighbors' Euclidean distances from u. It is however conceivable that the neighbor order can reflect a much more general notion of link quality, such as signal attenuation or packet arrival rate.
Phase b: Neighbor order exchange: the neighbor order information is exchanged among all neighbors. Typically a node u broadcasts its own neighbor order while receiving the order established by all of its neighbors. Phase c: Edge selection: each node locally selects those neighboring nodes which will form its neighborhood in the resulting topology control graph, based on the previously exchanged neighbor order information.
For this purpose a node u traverses neighbor order with decreasing link quality. Informally speaking, a node u only builds a direct communication link to a neighbor v if u has no "better" neighbor w that can be reached more easily from v than u itself. We explain in the following how nodes order can be obtained in XTC.
Weights of the edges can be realized by having each node initially transmitting a control signal together with a message containing information on the control signal transmission power. With the additional assumption that the employed antennas are isotropic and that the signal can propagate without obstruction, the control signal receivers can compute an order over the Euclidean distance to the senders from the receiving and transmission power levels.
If all nodes send with equal transmission power, the neighbor order of u is even equivalent to the relative order of only the receive power levels sensed at a node u if the edge weights are considered link quality indicators in a more general sense, these weights and consequently the neighbor ordering can be established by exchange of probe messages.
In contrast to typical topology control algorithms based on node positions, XTC does not include the edge u, w in its result graph, but exploits that a better connection exists via node v. An example of link selection in XTC. Every node communicates with its neighbors in the network not more than twice.
While previously proposed topology control algorithms commonly assumed that exact node and neighbors positions information is available, by means of GPS for example, XTC does not require this assumption. The algorithm works with a general notion of a quality order over a node's neighbors. It also does not assume the network graph to be a unit disk graph; XTC was shown to work on general weighted network graph too.
In the special case of the network graph being a Unit Disk Graph, the resulting topology proves to have bounded degree at most 6, connected, and planar no two intersected edges in the topology.
On average case, the resultant graph is a good spanner, and as being planar, it lends itself for geometric routing. By nodes, randomly distributed over an area of adapting the power to send a message over m by m. The second subplot, the unit shorter links, permitted by the topology control disk graph, represents all possible links algorithm, the overall power consumptions for between the nodes, given that the maximum sending messages will be reduced.
The transmission range is 50m. The other subplots drawback of topology control is the reduction represent the graphs obtained by a given of the throughput and the increased delay due topology control algorithm. That model follows the formula 2. The Yao Graph is a direction based algorithm. The space around every point is subdivided into cones. In each cone the node selects the closest node to connect itself.
The XTC graph [4] is obtained in three stages. Firstly every node gives a ranking to each neighbour. This ranking can be done based on different parameters, like distance or path loss. Secondly the neighbours exchange their ranked list of neighbours. Finally, the nodes select some connections. The selection is made as follows: every node neighbour is Figure 3.
Algorithms for topology control examined in the order according to the ranking. If a candidate ranked an already The Minimum Spanning Tree MST examined node higher than the node, the node algorithm connects all nodes avoiding the will not connect with that candidate. For formation of closed circuits. A local selection of a link is consistent in both version of the algorithm exists and the directions, meaning that if u selects a link to v, algorithm can be based on the path loss i.
This Local MST. In order to study and compare the different The Gabriel Graph connects two nodes u algorithms described in the previous section, a and v, on condition that there is no node inside program has been written in Matlab, the circle centred on the centre between u and implementing the graphs obtained by the v and with a diameter that equals the distance different algorithms.
The user interface of the between those nodes. The Delaunay Triangulation, is the dual of The comparison of the algorithms is based the Voronoi Diagram [3] and connects the on three parameters: the practicability, the nodes u and v if a circle with uv as chord exists node degree and the energy efficiency.
To have a practical topology control The Minimum Power Topology is an algorithm, which can be implemented on a real algorithm that connects the nodes u and v if the WSN, two conditions must be fulfilled by following expression holds true for any other preference: first the algorithm must be node w: distributed. From all the above message over the distance xy. A first observation is the similarity between on the path loss. This can be easily explained.
Hence the XTC algorithm will yield the same ranking of the nodes. Program implementing the topology control but uses a different parameter to rank the algorithms nodes. Also the Gabriel Graph, based on distances The second parameter is the node degree between the nodes, and the Minimum Power [2]. The node degree is defined as the average topology algorithm, based on the path loss number of neighbours of each node. Fewer between the nodes, results in the same graph.
However the attenuation factor in the path loss, the node degree may not be too small to guarantee condition to select a connection stays the same a sufficient degree of redundancy in the for both algorithms.
Figure 5 shows the mean node degree for a number of nodes N going from 10 to 30, for different algorithms. MST seems to be a bad choice for WSN, because of the So far the comparison of the algorithms lack of redundancy in the network.
The node showed that the best choice for a topology degree tends to 2 by definition. Hence, if one control algorithm is the XTC or the Minimum link is down, the network will immediately be Power Topology algorithm. To compare the energy efficiency of the XTC and the MPT algorithms, a random constellation of N nodes on a m by m area was generated over 50 times, with N varying from 5 to The transmission range of the nodes was set to 50m.
For each constellation the XTC and the MPT topology was determined and the mean power needed to send a message from all nodes to all the other nodes was calculated on both topologies.
The power ratio is the ratio of power used A third way to compare the topology with an algorithm for topology control to the algorithms is based on the energy efficiency.
Hence This will be the subject of the next section. The hardware platform that is used as Figure 6. The Tmote Sky Figure 6 shows the results for the power platform is a wireless sensor node based on a ratio for ascending node densities N varying TI MSP microcontroller with an In the simulation, the compatible [6] radio chip CC from attenuation factor for the path loss was set to 2.
The Tmote Sky platform offers a algorithm is slightly more efficient than the number of integrated peripherals including a XTC algorithm, although the difference is bit ADC and DAC and a number of small. In both cases the gain in power integrated sensors like a temperature sensor, 2 consumption increases with N and goes up to light sensors and a humidity sensor.
The stretch factor is the ratio of the power needed when using topology control to the minimally possible needed power.
The more the mean stretch factor tends to 1, the more the algorithm is efficient. Figure 7 shows the mean stretch factor for the two topologies. Figure 8. Tmote Sky platform The real-time operating system used on the nodes is Contiki 2. Contiki is an open source multi-tasking operating system for networked systems. It is designed for embedded systems with small amounts of memory. Contiki permits to use of two different communication stacks: uIP and Rime.
Figure 7. Therefore Rime is used in our implementation. In general a topology control algorithm is implemented between the second and third layer of the ISO model. It uses the link layer to connect with its direct neighbours and exchange information with them. This information will be used to build the topology of the network. The network layer will only see the neighbours permitted by the topology Figure 9.
Netsim: simulation without topology control control. For the implementation, the XTC algorithm was chosen. The principle of the implementation is as follows: each node periodically broadcast messages to its direct neighbours.
In a first step these messages are used to build an up-to-date list of possible neighbours and their corresponding RSSIs. In a second step this list is send to all neighbours.
0コメント