what is wireless sensor network
large number of heterogeneous sensor devices spread over large area
The main function
wireless sensing + data networking
group of sensors linked by wireless media to preform distributed sensing task
Components of a WSN Node
A WSN node contains several technical components. These include the radio, battery, microcontroller, analog circuit,and sensor interface. When using WSN radio technology, you must make important trade-offs. In battery-powered systems, higher radio data rates and more frequent radio use consume more power. Often three years of battery life is a requirement, so many of the WSN systems today are based on ZigBee due to its low-power consumption. Because battery life and power management technology are constantly evolving and because of the available IEEE 802.11 bandwidth, Wi-Fi is an interesting technology. The second technology consideration for WSN systems is the battery. In addition to long life requirements, you must consider the size and weight of batteries as well as international standards for shipping batteries and battery availability. The low cost and wide availability of carbon zinc and alkaline batteries make them a common choice. To extend battery life, a WSN node periodically wakes up and transmits data by powering on the radio and then powering it back off to conserve energy. WSN radio technology must efficiently transmit a signal and allow the system to go back to sleep with minimal power use. This means the processor involved must also be able to wake, power up, and return to sleep mode efficiently. Microprocessor trends for WSNs include reducing power consumption while maintaining or increasing processor speed. Much like your radio choice, the power consumption and processing speed trade-off is a key concern when selecting a processor for WSNs. This makes the x86 architecture a difficult option for
battery-powered devices
meduim acess control in IEEE 802.15.4
-super frame structure
The MAC sublayer provides two services: the MAC data service and the MAC management service
interfacing to the MAC sublayer management entity (MLME) service access point (SAP) (MLMESAP).The MAC data service enables the transmission and reception of MAC protocol data units (MPDU) across the PHY data service.
The features of MAC sublayer are beacon management, channel access, GTS management,
frame validation, acknowledged frame delivery, association and disassociation.
routing layer in wsn
AODV: Ad hoc On Demand Distance Vector
AODV is a pure on-demand route acquisition algorithm: nodes that do not lie on active paths neither maintain any routing information nor participate in any periodic routing table exchanges. Further, a node does not have to discover and maintain a route to another node until the two need to communicate, unless the former node is offering services as an intermediate forwarding station to maintain connectivity between two other nodes.
application of wsn
The applications of IEEE 802.15.4 based networks are wide ranging, covering both industrial and domestic use. Essentially, for IEEE 802.15.4 to be used in a networking solution, the required data rate must be low (≤ 250 kbps) and the maximum range for communicating devices must be short. In addition, a device with an autonomous power supply (no power cables) must have an extremely low power consumption. If these criteria are met, IEEE 802.15.4 may provide the ideal networking solution, particularly when cost and installation are significant issues.
A number of fields of application of IEEE 802.15.4 are described below.
• Home Automation and Security:
A wireless PAN provides a low-cost solution for electronic control within the home; e.g. HVAC (heating, ventilation and air-conditioning), lighting, curtains/blinds, doors, locks, home entertainment systems. Another important application within the home is security – both intruder and fire detection.
• Consumer products:
Wireless PANs can be built into consumer electronics products. The most obvious example is to provide a common remote control for the various components of a home entertainment system (that may be distributed throughout the home). Other examples are computer systems and toys, in which a wireless radio link may be used to replace a point-to-point cable link (such as between a mouse and a PC).
• Healthcare:
This field employs sensors and diagnostic devices that can be networked by means of a wireless PAN. Applications include monitoring during healthcare programmes such as fitness training, in addition to medical applications.
• Vehicle Monitoring:
Vehicles usually contain many sensors and diagnostic devices, and provide ideal applications for wireless PANs. A prime example is the use of pressure sensors in tyres, which cannot be connected by cables.
• Agriculture:
Wireless PANs can help farmers monitor land and environmental conditions in order to optimise their crop yields. Such networks can operate at very low data rates and latencies, but require wide geographical coverage – the latter issue is addressed by using network topologies that allow the relaying of messages across the network.
IEEE 802.15.4 MAC
The MAC sublayer provides two services: the MAC data service and the MAC management service interfacing to the MAC sublayer management entity (MLME) service access point (SAP) (MLMESAP). The MAC data service enables the transmission and reception of MAC protocol data units (MPDU) across the PHY data service. The features of MAC sublayer are beacon management, channel access, GTS management, frame validation, acknowledged frame delivery, association and disassociation.
1 Superframe Structure
LR-WPAN allows the optional use of a superframe structure. The format of the superframe is
defined by the coordinator. The superframe is bounded by network beacons and is divided into equally sized slots. The beacon frame is sent in the first slot of each superframe. If a coordinator does not want to use the superframe structure, it may turn off the beacon transmissions. The beacons are used to synchronize the attached devices, to identify the PAN and to describe the structure of superframes.
The superframe can have an active and an inactive portion. During the inactive portion, the coordinator shall not interact with its PAN and may enter a low-power mode. The active portion portion consists of contention access period (CAP) and contention free period (CFP). Any device wishing to communicate during the CAP shall compete with other devices using a slotted CSMACA mechanism. On the other hand, the CFP contains guaranteed time slots (GTSs). The GTSs always appear at the end of the active superframe starting at a slot boundary immediately following the CAP. The PAN coordinator may allocate up to seven of these GTSs and a GTS can occupy more than one slot period.
The duration of different portions of the superframe are described by the values of macBeaconOrder and macSuperFrameOrder. macBeaconOrder describes the interval at which the coordinator shall transmit its beacon frames. The beacon interval, BI, is related to the macBeaconOrder, BO, as follows: BI = aBaseSuperFrameDuration2BO, 0 BO 14. The superframe is ignored if BO = 15.
The value of macSuperFrameOrder describes the length of the active portion of the superframe. The superframe duration, SD, is related to macSuperFrameOrder, SO, as follows: SD = aBaseSuperFrameDuration2SO, 0 SO 14. If SO = 15, the superframe should not remain active after the beacon. The active portion of each superframe is divided into a aNumSuperFrameSlots equally spaced slots of duration 2SOaBaseSlotDuration and is composed of three parts: a beacon, a CAP and
Figure 1: An example superframe structure.
CFP. The beacon is transmitted at the start of slot 0 without the use of CSMA. The CAP starts immediately after the beacon. The CAP shall be at least aMinCAPLength symbols unless additional space is needed to temporarily accommodate the increase in the beacon frame length to perform GTS maintenance. All frames except acknowledgement frames or any data frame that immediately follows the acknowledgement of a data request command that are transmitted in the CAP shall use slotted CSMA-CA to access the channel. A transmission in the CAP shall be complete one IFS period before the end of the CAP. If this is not possible, it defers its transmission until the CAP of the following superframe. An example superframe structure is shown in Figure 1. The CFP, if present, shall start on a slot boundary immediately following the CAP and extends to the end of the active portion of the superframe. The length of the CFP is determined by the total length of all of the combined GTSs. No transmissions within the CFP shall use a CSMA-CA mechanism. A device transmitting in the CFP shall ensure that its transmissions are complete one IFS period before the end of its GTS. IFS time is the amount of time necessary to process the received packet by the PHY. Transmitted frames shall be followed by an IFS period. The length of IFS depends on the size of the frame that has just been transmitted. Frames of up to aMaxSIFSFrameSize in length shall be followed by a SIFS whereas frames of greater length shall be followed by a LIFS The PANs that do not wish to use the superframe in a nonbeacon-enabled shall set both macBeaconOrder and macSuperFrameOrder to 15. In this kind of network, a coordinator shall not transmit any beacons, all transmissions except the acknowledgement frame shall use unslotted CSMA-CA to access channel, GTSs shall not be permitted.
2 CSMA-CA Algorithm
If superframe structure is used in the PAN, then slotted CSMA-CA shall be used. If beacons are not being used in the PAN or a beacon cannot be located in a beacon-enabled network, unslotted CSMA-CA algorithm is used. In both cases, the algorithm is implemented using units of time called backoff periods, which is equal to aUnitBackoffPeriod symbols. In slotted CSMA-CA channel access mechanism, the backoff period boundaries of every device in the PAN are aligned with the superframe slot boundaries of the PAN coordinator. In slotted CSMA-CA, each time a device wishes to transmit data frames during the CAP, it shall locate the boundary of the next backoff period. In unslotted CSMA-CA, the backoff periods of one device do not need to be synchronized to the backoff periods of another device. Each device has 3 variables: NB, CW and BE. NB is the number of times the CSMA-CA algorithm was required to backoff while attempting the current transmission. It is initialized to 0 before every new transmission. CW is the contention window length, which defines the number of backoff periods that need to be clear of activity before the transmission can start. It is initialized to 2 before each transmission attempt and reset to 2 each time the channel is assessed to be busy. CW is only used for slotted CSMA-CA. BE is the backoff exponent, which is related to how many backoff periods a device shall wait before attempting to assess the channel. Although the receiver of the device is enabled during the channel assessment portion of this algorithm, the device shall discard any frames received during this time. In slotted CSMA-CA, NB, CW and BE are initialized and the boundary of the next backoff period is located. In unslotted CSMA-CA, NB and BE are initialized (step1). The MAC layer shall delay for a random number of complete backoff periods in the range 0 to 2BE − 1 (step 2) then request that PHY performs a CCA (clear channel assessment) (step 3). The MAC sublayer shall then proceed if the remaining CSMA-CA algorithm steps, the frame transmission, and any acknowledgement can be completed before the end of the CAP. If theMAC sublayer cannot proceed, it shall wait until the start of the CAP in the next superframe and repeat the evaluation. If the channel is assessed to be busy (step 4), the MAC sublayer shall increment both NB and BE by one, ensuring that BE shall be no more than aMaxBE. In slotted CSMA-CA, CWcan also be reset to 2. If the value of NB is less than or equal to macMaxCSMABackoffs, the CSMA-CA shall return to step 2, else the CSMA-CA shall terminate with a Channel Access Failure status. If the channel is assessed to be idle (step 5), in a slotted CSMA-CA, the MAC sublayer shall ensure that contention window is expired before starting transmission. For this, the MAC sublayer first decrements CW by one. If CW is not equal to 0, go to step 3 else start transmission on the boundary of the next backoff period. In the unslotted CSMA-CA, the MAC sublayer start transmission immediately if the channel is assessed to be idle. The whole CSMA-CA algorithm is illustrated in Figure 2.
3 Data Transfer model
Three types of data transfer transactions exist: from a coordinator to a device, from a device to acoordinator and between two peer devices. The mechanism for each of these transfers depend on whether the network supports the transmission of beacons. When a device wishes to transfer data in a nonbeacon-enabled network, it simply transmits its data frame, using the unslotted CSMA-CA, to the coordinator. There is also an optional acknowledgement at the end. When a device wishes to transfer data to a coordinator in a beacon-enabled network, it first listens for the network beacon. When the beacon is found, it synchronizes to the superframe structure. At the right time, it transmits its data frame, using slotted CSMA-CA, to the coordinator. There is an optional acknowledgement at the end as shown in Figure 4.4. The applications transfers are completely controlled by the devices on a PAN rather than by the coordinator. This provides the energy-conservation feature of the ZigBee network. When a coordinator wishes to transfer data to a device in a beacon-enabled network, it indicates in the network beacon that the data message is pending. The device periodically listens to the network beacon, and if a message is pending, transmits a MAC command requesting this data, using slotted CSMA-CA. The coordinator optionally acknowledges the successful transmission of this packet. The pending
Figure 2: The CSMA-CA algorithm.
data frame is then sent using slotted CSMA-CA. The device acknowledged the successful reception of the data by transmitting an acknowledgement frame. Upon receiving the acknowledgement, the message is removed from the list of pending messages in the beacon When a coordinator wishes to transfer data to a device in a nonbeacon enabled network, it stores the data for the appropriate device to make contact and request data. A device may make contact by transmitting a MAC command requesting the data, using unslotted CSMA-CA, to its coordinator at an application-defined rate. The coordinator acknowledges this packet. If data are pending, the coordinator transmits the data frame using unslotted CSMA-CA. If data are not pending, the coordinator transmits a data frame with a zero-length payload to indicate that no data were pending. The device acknowledges this packet a. In a peer-to-peer network, every device can communicate with any other device in its transmission radius. There are two options for this. In the first case, the node will listen constantly and transmit its data using unslotted CSMA-CA. In the second case, the nodes synchronize with each other so that they can save power.
The MAC sublayer provides two services: the MAC data service and the MAC management service interfacing to the MAC sublayer management entity (MLME) service access point (SAP) (MLMESAP). The MAC data service enables the transmission and reception of MAC protocol data units (MPDU) across the PHY data service. The features of MAC sublayer are beacon management, channel access, GTS management, frame validation, acknowledged frame delivery, association and disassociation.
1 Superframe Structure
LR-WPAN allows the optional use of a superframe structure. The format of the superframe is
defined by the coordinator. The superframe is bounded by network beacons and is divided into equally sized slots. The beacon frame is sent in the first slot of each superframe. If a coordinator does not want to use the superframe structure, it may turn off the beacon transmissions. The beacons are used to synchronize the attached devices, to identify the PAN and to describe the structure of superframes.
The superframe can have an active and an inactive portion. During the inactive portion, the coordinator shall not interact with its PAN and may enter a low-power mode. The active portion portion consists of contention access period (CAP) and contention free period (CFP). Any device wishing to communicate during the CAP shall compete with other devices using a slotted CSMACA mechanism. On the other hand, the CFP contains guaranteed time slots (GTSs). The GTSs always appear at the end of the active superframe starting at a slot boundary immediately following the CAP. The PAN coordinator may allocate up to seven of these GTSs and a GTS can occupy more than one slot period.
The duration of different portions of the superframe are described by the values of macBeaconOrder and macSuperFrameOrder. macBeaconOrder describes the interval at which the coordinator shall transmit its beacon frames. The beacon interval, BI, is related to the macBeaconOrder, BO, as follows: BI = aBaseSuperFrameDuration2BO, 0 BO 14. The superframe is ignored if BO = 15.
The value of macSuperFrameOrder describes the length of the active portion of the superframe. The superframe duration, SD, is related to macSuperFrameOrder, SO, as follows: SD = aBaseSuperFrameDuration2SO, 0 SO 14. If SO = 15, the superframe should not remain active after the beacon. The active portion of each superframe is divided into a aNumSuperFrameSlots equally spaced slots of duration 2SOaBaseSlotDuration and is composed of three parts: a beacon, a CAP and
Figure 1: An example superframe structure.CFP. The beacon is transmitted at the start of slot 0 without the use of CSMA. The CAP starts immediately after the beacon. The CAP shall be at least aMinCAPLength symbols unless additional space is needed to temporarily accommodate the increase in the beacon frame length to perform GTS maintenance. All frames except acknowledgement frames or any data frame that immediately follows the acknowledgement of a data request command that are transmitted in the CAP shall use slotted CSMA-CA to access the channel. A transmission in the CAP shall be complete one IFS period before the end of the CAP. If this is not possible, it defers its transmission until the CAP of the following superframe. An example superframe structure is shown in Figure 1. The CFP, if present, shall start on a slot boundary immediately following the CAP and extends to the end of the active portion of the superframe. The length of the CFP is determined by the total length of all of the combined GTSs. No transmissions within the CFP shall use a CSMA-CA mechanism. A device transmitting in the CFP shall ensure that its transmissions are complete one IFS period before the end of its GTS. IFS time is the amount of time necessary to process the received packet by the PHY. Transmitted frames shall be followed by an IFS period. The length of IFS depends on the size of the frame that has just been transmitted. Frames of up to aMaxSIFSFrameSize in length shall be followed by a SIFS whereas frames of greater length shall be followed by a LIFS The PANs that do not wish to use the superframe in a nonbeacon-enabled shall set both macBeaconOrder and macSuperFrameOrder to 15. In this kind of network, a coordinator shall not transmit any beacons, all transmissions except the acknowledgement frame shall use unslotted CSMA-CA to access channel, GTSs shall not be permitted.
2 CSMA-CA Algorithm
If superframe structure is used in the PAN, then slotted CSMA-CA shall be used. If beacons are not being used in the PAN or a beacon cannot be located in a beacon-enabled network, unslotted CSMA-CA algorithm is used. In both cases, the algorithm is implemented using units of time called backoff periods, which is equal to aUnitBackoffPeriod symbols. In slotted CSMA-CA channel access mechanism, the backoff period boundaries of every device in the PAN are aligned with the superframe slot boundaries of the PAN coordinator. In slotted CSMA-CA, each time a device wishes to transmit data frames during the CAP, it shall locate the boundary of the next backoff period. In unslotted CSMA-CA, the backoff periods of one device do not need to be synchronized to the backoff periods of another device. Each device has 3 variables: NB, CW and BE. NB is the number of times the CSMA-CA algorithm was required to backoff while attempting the current transmission. It is initialized to 0 before every new transmission. CW is the contention window length, which defines the number of backoff periods that need to be clear of activity before the transmission can start. It is initialized to 2 before each transmission attempt and reset to 2 each time the channel is assessed to be busy. CW is only used for slotted CSMA-CA. BE is the backoff exponent, which is related to how many backoff periods a device shall wait before attempting to assess the channel. Although the receiver of the device is enabled during the channel assessment portion of this algorithm, the device shall discard any frames received during this time. In slotted CSMA-CA, NB, CW and BE are initialized and the boundary of the next backoff period is located. In unslotted CSMA-CA, NB and BE are initialized (step1). The MAC layer shall delay for a random number of complete backoff periods in the range 0 to 2BE − 1 (step 2) then request that PHY performs a CCA (clear channel assessment) (step 3). The MAC sublayer shall then proceed if the remaining CSMA-CA algorithm steps, the frame transmission, and any acknowledgement can be completed before the end of the CAP. If theMAC sublayer cannot proceed, it shall wait until the start of the CAP in the next superframe and repeat the evaluation. If the channel is assessed to be busy (step 4), the MAC sublayer shall increment both NB and BE by one, ensuring that BE shall be no more than aMaxBE. In slotted CSMA-CA, CWcan also be reset to 2. If the value of NB is less than or equal to macMaxCSMABackoffs, the CSMA-CA shall return to step 2, else the CSMA-CA shall terminate with a Channel Access Failure status. If the channel is assessed to be idle (step 5), in a slotted CSMA-CA, the MAC sublayer shall ensure that contention window is expired before starting transmission. For this, the MAC sublayer first decrements CW by one. If CW is not equal to 0, go to step 3 else start transmission on the boundary of the next backoff period. In the unslotted CSMA-CA, the MAC sublayer start transmission immediately if the channel is assessed to be idle. The whole CSMA-CA algorithm is illustrated in Figure 2.
3 Data Transfer model
Three types of data transfer transactions exist: from a coordinator to a device, from a device to acoordinator and between two peer devices. The mechanism for each of these transfers depend on whether the network supports the transmission of beacons. When a device wishes to transfer data in a nonbeacon-enabled network, it simply transmits its data frame, using the unslotted CSMA-CA, to the coordinator. There is also an optional acknowledgement at the end. When a device wishes to transfer data to a coordinator in a beacon-enabled network, it first listens for the network beacon. When the beacon is found, it synchronizes to the superframe structure. At the right time, it transmits its data frame, using slotted CSMA-CA, to the coordinator. There is an optional acknowledgement at the end as shown in Figure 4.4. The applications transfers are completely controlled by the devices on a PAN rather than by the coordinator. This provides the energy-conservation feature of the ZigBee network. When a coordinator wishes to transfer data to a device in a beacon-enabled network, it indicates in the network beacon that the data message is pending. The device periodically listens to the network beacon, and if a message is pending, transmits a MAC command requesting this data, using slotted CSMA-CA. The coordinator optionally acknowledges the successful transmission of this packet. The pending
Figure 2: The CSMA-CA algorithm.
data frame is then sent using slotted CSMA-CA. The device acknowledged the successful reception of the data by transmitting an acknowledgement frame. Upon receiving the acknowledgement, the message is removed from the list of pending messages in the beacon When a coordinator wishes to transfer data to a device in a nonbeacon enabled network, it stores the data for the appropriate device to make contact and request data. A device may make contact by transmitting a MAC command requesting the data, using unslotted CSMA-CA, to its coordinator at an application-defined rate. The coordinator acknowledges this packet. If data are pending, the coordinator transmits the data frame using unslotted CSMA-CA. If data are not pending, the coordinator transmits a data frame with a zero-length payload to indicate that no data were pending. The device acknowledges this packet a. In a peer-to-peer network, every device can communicate with any other device in its transmission radius. There are two options for this. In the first case, the node will listen constantly and transmit its data using unslotted CSMA-CA. In the second case, the nodes synchronize with each other so that they can save power.
Routing algorithm
can be thought of an hierarchical routing strategy with table-driven optimizations applied where possible. The routing layer is said to start with the well-studied publicdomain algorithm Ad hoc On Demand Distance Vector (AODV) and Motorola’s Cluster-Tree algorithm. We summarize AODV and Cluster-Tree in Section ??.
5.1 AODV: Ad hoc On Demand Distance Vector
AODV is a pure on-demand route acquisition algorithm: nodes that do not lie on active paths neithermaintain any routing information nor participate in any periodic routing table exchanges. Further, anode does not have to discover and maintain a route to another node until the two need to communicate,unless the former node is offering services as an intermediate forwarding station to maintainconnectivity between two other nodes.
The primary objectives of the algorithm are to broadcast discovery packets only when necessary,to distinguish between local connectivity management and general topology maintenance and to disseminate information about changes in local connectivity to those neighboring mobile nodes that are likely to need the information. When a source node needs to communicate with another node for which it has no routing information in its table, the Path Discovery process is initiated. Every node maintains two separate counters: sequence number and broadcast id. The source node initiates path discovery by broadcasting a route request (RREQ) packet to its neighbors, which includes source addr, source sequence number, broadcast id, dest addr, dest sequence number, hop cnt. (Source sequence number is for maintaining freshness information about the reverse route whereas the destination sequence number is for maintaining freshness of the route to the destination before it can be accepted by the source.) The pair source addr, broadcast id uniquely identifies a RREQ, where broadcast id is incremented whenever the source issues a new RREQ.When an intermediate node receives a RREQ, if it has already received a RREQ with the same broadcast id and source address, it drops the redundant RREQ and does not rebroadcast it. Otherwise, it rebroadcasts it to its own neighbors after increasing hop cnt. Each node keeps the following information: destination IP address, source IP address, broadcast id, expiration time for reverse path route entry and source node’s sequence number. As the RREQ travels from a source to destinations, it automatically sets up the reverse path from all nodes back to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of RREQ. These reverse path route entries are maintained for at least enough time for the RREQ to traverse the network and produce a reply to the sender.
Figure 5.1: Reverse and forward path formation in AODV protocol.
When the RREQ arrives at a node, possibly the destination itself, that possesses a current route to the destination, the receiving node first checks that the RREQ was received over a bi-directional link. If this node is not destination but has route to the destination, it determines whether the route is current by comparing the destination sequence number in its own route entry to the destination sequence number in the RREQ. If RREQ’s sequence number for the destination is greater than that recorded by the intermediate node, the intermediate node must not use this route to respond to the RREQ, instead rebroadcasts the RREQ. If the route has a destination sequence number that is greater than that contained in the RREQ or equal to that contained in the RREQ but a smaller hop count, it can unicasts a route reply packet (RREP) back to its neighbor from which it received the RREQ. A RREP contains the following information: source addr, dest addr, dest sequence number, hop cnt and lifetime. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP came, updates its timeout information for route entries to the source and destination, and records the latest destination sequence number for the requested destination. Nodes that are along the path determined by the RREP will timeout after route request expiration timer and will delete the reverse pointers since they are not on the path from source to destination as shown in Figure 5.1. The value of this timeout time depends on the size of the ad hoc network. Also, there is the routing caching timeout that is associated with each routing entry to show the time after which the route is considered to be invalid. Each time a route entry is used to transmit data from a source toward a destination, the timeout for the entry is reset to the current time plus active-route-timeout. The source node can begin data transmission as soon as the first RREP is received, and can later update its routing informa ion if it learns of a better route. Each routing table entry includes the following fields: destination, next hop, number of hops (metric), sequence number for the destination, active neighbors for this route, expiration time for the route table entry. For path maintenance, each node keeps the address of active neighborsthrough which packets for the given destination are received is maintained. This neighbor is considered active if it originates or relays at least one packet for that destination within the last active-timeout period. Once the next hop on the path from source to the destination becomes unreachable (hello messages are not received for a certain time, hello messages also ensures that only nodes with bidirectional connectivity are considered to be neighbors, therefore each hello message included the nodes from which the node has heard), the node upstream of the break propagates an unsolicited RREP with a fresh sequence number and hop count of 1to all active upstream nodes. This process continues until all active source nodes are notified. Upon receiving the notification of a broken link, the source nodes can restart the discovery process if they still require a route to the destination. If it decides that it would like to rebuild the route to the destination, it sends out an RREQ with a destination sequence number of one greater than the previously known sequence number, to ensure that it builds a new, viable route and that no nodes reply if they still regard the previous route as valid.
5.2 Cluster-Tree Algorithm
The cluster-tree protocol is a protocol of the logical link and network layers that uses link-state packets to form either a single cluster network or a potentially larger cluster tree network. The network is basically self-organized and supports network redundancy to attain a degree of fault resistance and self-repair. Nodes select a cluster head and form a cluster according to the self-organized manner. Then self-developed clusters connect to each other using the Designated Device (DD).
5.2.1 Single Cluster Network
The cluster formation process begins with cluster head selection. After a cluster head is selected , the cluster head expands links with other member nodes to form a cluster. After a node turns on, it scans the channels to search for a HELLO message form other nodes (HELLO messages correspond to beacons in MAC layer of IEEE 802.15.4). If it can’t get any HELLO messages for a certain time, then it turns to a cluster head as shown in Figure 5.2 and sends out HELLO messages to its neighbors. The new cluster head wait for responses from neighbors for a while. If it hasn’t received any connection requests, it turns back to a regular node and listens again. The cluster head can also be selected based on stored parameters of each node, like transmission
range, power capacity, computing ability or location information. After becoming the cluster head (CH), the node broadcasts a periodic HELLO message that contains a part of the cluster head MAC address and node ID 0 that indicates the cluster head. The nodes that receive this message send a CONNECTION REQUEST message to the cluster head. When the CH receives it, it responds to the node with a CONNECTION RESPONSE message that contains a node ID for the node (node ID corresponds to the short address at the MAC layer). The node that is assigned a node ID replies with an ACK message to the cluster head. The message exchange is shown in Figure 5.3. If all nodes are located in the range of the cluster head, the topology of connection becomes a star and every member nodes are connected to the cluster head with one hop. A cluster can expand into a multi-hop structure when each node supports multiple connections. The message exchange for the multihop cluster set up procedure is shown in Figure 5.4. If the cluster head has run out of all node IDs or the cluster has reached some other defined limit, it should reject connection requests from new nodes. The rejection is through the assignment of a special ID to the node. The entry of the neighbor list and the routes is updated by the periodic HELLO message. If a node entry does not update until a certain timeout limit, it should be eliminated.
Figure 5.2: Cluster head selection process.
A node may receive a HELLO message from a node that belongs to different cluster. In that case, the node adds the cluster ID (CID) of the transmitting node in the neighbor list and then sends it inside a LINK STATE REPORT to the CH so that CH knows which clusters its cluster hasintersection. The LINK STATE REPORT message also contain the neighbors node ID list of the node so that the CH knows the complete topology to make topology optimizations. If the topology change is required, then the CH sends a TOPOLOGY UPDATE message. If a member receives a TOPOLOGY UPDATE message that the different parent node is linked to the node, it changes the parent node as indicated in the message. And it also records its child nodes and the nodes below it in the tree at this time. If a member node has trouble and becomes unable to communicate, the tree route of the cluster would be reconfigured. The CH know the presence of a trouble by the periodic LINK STATE REPORT.When the cluster head has trouble, the distribution of HELLO message is stopped and all member nodes know that they have lost the CH. The cluster would then be reconfigured in the same way as the cluster formation process.
5.2.2 Multi-Cluster Network
To form a network, a Designated Device (DD) is needed. The DD has responsibility to assign a unique cluster ID to each cluster head. This cluster ID combined with the node ID that the CH assigns to each node within a cluster forms a logical address and is used to route packets. Another role of the DD is to calculate the shortest route from the cluster to the DD and inform it to all nodes within the network. When the DD joins the network, it acts as the CH of cluster 0 and starts to send HELLO message to the neighborhood. If a CH has received this message, it sends a CONNECTION REQUEST message and joins the cluster 0. After that, the CH requests a CID to the DD. In this case, the CH is
Figure 5.3: Link setup between CH and member node.
a border node that has two logical addresses. One is for a member of the cluster 0 and the other is for a CH. When the CH gets a new CID, it informs its member nodes by the HELLO message. If a member has received the HELLO message from the DD, it adds CID 0 in its neighbor list and reports to its CH. The reported CH selects the member node as a border node to its parent cluster and sends a NETWORK CONNECTION REQUEST message to the member node to set up a connection with the DD. The border node requests a connection and joins the cluster 0 as its member node. Then it sends a CID REQUEST message to the DD. After the CID RESPONSE message arrival, the border node sends NETWORK CONNECTION RESPONSE message that contains a new CID to the CH.When the CH gets a new CID, it informs to its member nodes by the HELLO message.
The clusters not bordering cluster 0 use intermediate clusters to get a CID. Again, either the CH becomes the border node to its parent cluster or the CH names a member node as the border to its parent cluster. These processes are shown in Figures 5.5,5.6,5.7,5.8. Each member node of the cluster has to record its parent cluster, child/lower clusters and the border node IDs associated with both the parent and child clusters. The DD should store the whole tree structure of the clusters. Like the nodes in the clusters, the CHs report their link state information to the DD. The CH periodically sends a NETWORK LINK STATE REPORT message that contains its neighbor cluster CID list to the DD. Then this information can be used to calculate the optimized route and periodically update the topology for the network redundancy. In the same way, the DD can send TOPOLOGY UPDATE message to inform up-to-date route from the DD to the clusters. A backup DD (BDD) can be prepared to prevent network down time due to the DD trouble. Inter-cluster communication, which is shown in Figure 5.9, is realized by routing. The border nodes act as routers that connect clusters and relay packets between the clusters. When a border node receives a packet, it examines the destination address, then forwards to the next border node in the adjacent cluster or to the destination node within the cluster. Only the DD can send a message to all the nodes within its network. The message is forwarded along the tree route of clusters. The border node should forward the broadcast packet from the
can be thought of an hierarchical routing strategy with table-driven optimizations applied where possible. The routing layer is said to start with the well-studied publicdomain algorithm Ad hoc On Demand Distance Vector (AODV) and Motorola’s Cluster-Tree algorithm. We summarize AODV and Cluster-Tree in Section ??.
5.1 AODV: Ad hoc On Demand Distance Vector
AODV is a pure on-demand route acquisition algorithm: nodes that do not lie on active paths neithermaintain any routing information nor participate in any periodic routing table exchanges. Further, anode does not have to discover and maintain a route to another node until the two need to communicate,unless the former node is offering services as an intermediate forwarding station to maintainconnectivity between two other nodes.
The primary objectives of the algorithm are to broadcast discovery packets only when necessary,to distinguish between local connectivity management and general topology maintenance and to disseminate information about changes in local connectivity to those neighboring mobile nodes that are likely to need the information. When a source node needs to communicate with another node for which it has no routing information in its table, the Path Discovery process is initiated. Every node maintains two separate counters: sequence number and broadcast id. The source node initiates path discovery by broadcasting a route request (RREQ) packet to its neighbors, which includes source addr, source sequence number, broadcast id, dest addr, dest sequence number, hop cnt. (Source sequence number is for maintaining freshness information about the reverse route whereas the destination sequence number is for maintaining freshness of the route to the destination before it can be accepted by the source.) The pair source addr, broadcast id uniquely identifies a RREQ, where broadcast id is incremented whenever the source issues a new RREQ.When an intermediate node receives a RREQ, if it has already received a RREQ with the same broadcast id and source address, it drops the redundant RREQ and does not rebroadcast it. Otherwise, it rebroadcasts it to its own neighbors after increasing hop cnt. Each node keeps the following information: destination IP address, source IP address, broadcast id, expiration time for reverse path route entry and source node’s sequence number. As the RREQ travels from a source to destinations, it automatically sets up the reverse path from all nodes back to the source. To set up a reverse path, a node records the address of the neighbor from which it received the first copy of RREQ. These reverse path route entries are maintained for at least enough time for the RREQ to traverse the network and produce a reply to the sender.
Figure 5.1: Reverse and forward path formation in AODV protocol.
When the RREQ arrives at a node, possibly the destination itself, that possesses a current route to the destination, the receiving node first checks that the RREQ was received over a bi-directional link. If this node is not destination but has route to the destination, it determines whether the route is current by comparing the destination sequence number in its own route entry to the destination sequence number in the RREQ. If RREQ’s sequence number for the destination is greater than that recorded by the intermediate node, the intermediate node must not use this route to respond to the RREQ, instead rebroadcasts the RREQ. If the route has a destination sequence number that is greater than that contained in the RREQ or equal to that contained in the RREQ but a smaller hop count, it can unicasts a route reply packet (RREP) back to its neighbor from which it received the RREQ. A RREP contains the following information: source addr, dest addr, dest sequence number, hop cnt and lifetime. As the RREP travels back to the source, each node along the path sets up a forward pointer to the node from which the RREP came, updates its timeout information for route entries to the source and destination, and records the latest destination sequence number for the requested destination. Nodes that are along the path determined by the RREP will timeout after route request expiration timer and will delete the reverse pointers since they are not on the path from source to destination as shown in Figure 5.1. The value of this timeout time depends on the size of the ad hoc network. Also, there is the routing caching timeout that is associated with each routing entry to show the time after which the route is considered to be invalid. Each time a route entry is used to transmit data from a source toward a destination, the timeout for the entry is reset to the current time plus active-route-timeout. The source node can begin data transmission as soon as the first RREP is received, and can later update its routing informa ion if it learns of a better route. Each routing table entry includes the following fields: destination, next hop, number of hops (metric), sequence number for the destination, active neighbors for this route, expiration time for the route table entry. For path maintenance, each node keeps the address of active neighborsthrough which packets for the given destination are received is maintained. This neighbor is considered active if it originates or relays at least one packet for that destination within the last active-timeout period. Once the next hop on the path from source to the destination becomes unreachable (hello messages are not received for a certain time, hello messages also ensures that only nodes with bidirectional connectivity are considered to be neighbors, therefore each hello message included the nodes from which the node has heard), the node upstream of the break propagates an unsolicited RREP with a fresh sequence number and hop count of 1to all active upstream nodes. This process continues until all active source nodes are notified. Upon receiving the notification of a broken link, the source nodes can restart the discovery process if they still require a route to the destination. If it decides that it would like to rebuild the route to the destination, it sends out an RREQ with a destination sequence number of one greater than the previously known sequence number, to ensure that it builds a new, viable route and that no nodes reply if they still regard the previous route as valid.
5.2 Cluster-Tree Algorithm
The cluster-tree protocol is a protocol of the logical link and network layers that uses link-state packets to form either a single cluster network or a potentially larger cluster tree network. The network is basically self-organized and supports network redundancy to attain a degree of fault resistance and self-repair. Nodes select a cluster head and form a cluster according to the self-organized manner. Then self-developed clusters connect to each other using the Designated Device (DD).
5.2.1 Single Cluster Network
The cluster formation process begins with cluster head selection. After a cluster head is selected , the cluster head expands links with other member nodes to form a cluster. After a node turns on, it scans the channels to search for a HELLO message form other nodes (HELLO messages correspond to beacons in MAC layer of IEEE 802.15.4). If it can’t get any HELLO messages for a certain time, then it turns to a cluster head as shown in Figure 5.2 and sends out HELLO messages to its neighbors. The new cluster head wait for responses from neighbors for a while. If it hasn’t received any connection requests, it turns back to a regular node and listens again. The cluster head can also be selected based on stored parameters of each node, like transmission
range, power capacity, computing ability or location information. After becoming the cluster head (CH), the node broadcasts a periodic HELLO message that contains a part of the cluster head MAC address and node ID 0 that indicates the cluster head. The nodes that receive this message send a CONNECTION REQUEST message to the cluster head. When the CH receives it, it responds to the node with a CONNECTION RESPONSE message that contains a node ID for the node (node ID corresponds to the short address at the MAC layer). The node that is assigned a node ID replies with an ACK message to the cluster head. The message exchange is shown in Figure 5.3. If all nodes are located in the range of the cluster head, the topology of connection becomes a star and every member nodes are connected to the cluster head with one hop. A cluster can expand into a multi-hop structure when each node supports multiple connections. The message exchange for the multihop cluster set up procedure is shown in Figure 5.4. If the cluster head has run out of all node IDs or the cluster has reached some other defined limit, it should reject connection requests from new nodes. The rejection is through the assignment of a special ID to the node. The entry of the neighbor list and the routes is updated by the periodic HELLO message. If a node entry does not update until a certain timeout limit, it should be eliminated.
Figure 5.2: Cluster head selection process.A node may receive a HELLO message from a node that belongs to different cluster. In that case, the node adds the cluster ID (CID) of the transmitting node in the neighbor list and then sends it inside a LINK STATE REPORT to the CH so that CH knows which clusters its cluster hasintersection. The LINK STATE REPORT message also contain the neighbors node ID list of the node so that the CH knows the complete topology to make topology optimizations. If the topology change is required, then the CH sends a TOPOLOGY UPDATE message. If a member receives a TOPOLOGY UPDATE message that the different parent node is linked to the node, it changes the parent node as indicated in the message. And it also records its child nodes and the nodes below it in the tree at this time. If a member node has trouble and becomes unable to communicate, the tree route of the cluster would be reconfigured. The CH know the presence of a trouble by the periodic LINK STATE REPORT.When the cluster head has trouble, the distribution of HELLO message is stopped and all member nodes know that they have lost the CH. The cluster would then be reconfigured in the same way as the cluster formation process.
5.2.2 Multi-Cluster Network
To form a network, a Designated Device (DD) is needed. The DD has responsibility to assign a unique cluster ID to each cluster head. This cluster ID combined with the node ID that the CH assigns to each node within a cluster forms a logical address and is used to route packets. Another role of the DD is to calculate the shortest route from the cluster to the DD and inform it to all nodes within the network. When the DD joins the network, it acts as the CH of cluster 0 and starts to send HELLO message to the neighborhood. If a CH has received this message, it sends a CONNECTION REQUEST message and joins the cluster 0. After that, the CH requests a CID to the DD. In this case, the CH is
Figure 5.3: Link setup between CH and member node.a border node that has two logical addresses. One is for a member of the cluster 0 and the other is for a CH. When the CH gets a new CID, it informs its member nodes by the HELLO message. If a member has received the HELLO message from the DD, it adds CID 0 in its neighbor list and reports to its CH. The reported CH selects the member node as a border node to its parent cluster and sends a NETWORK CONNECTION REQUEST message to the member node to set up a connection with the DD. The border node requests a connection and joins the cluster 0 as its member node. Then it sends a CID REQUEST message to the DD. After the CID RESPONSE message arrival, the border node sends NETWORK CONNECTION RESPONSE message that contains a new CID to the CH.When the CH gets a new CID, it informs to its member nodes by the HELLO message.
The clusters not bordering cluster 0 use intermediate clusters to get a CID. Again, either the CH becomes the border node to its parent cluster or the CH names a member node as the border to its parent cluster. These processes are shown in Figures 5.5,5.6,5.7,5.8. Each member node of the cluster has to record its parent cluster, child/lower clusters and the border node IDs associated with both the parent and child clusters. The DD should store the whole tree structure of the clusters. Like the nodes in the clusters, the CHs report their link state information to the DD. The CH periodically sends a NETWORK LINK STATE REPORT message that contains its neighbor cluster CID list to the DD. Then this information can be used to calculate the optimized route and periodically update the topology for the network redundancy. In the same way, the DD can send TOPOLOGY UPDATE message to inform up-to-date route from the DD to the clusters. A backup DD (BDD) can be prepared to prevent network down time due to the DD trouble. Inter-cluster communication, which is shown in Figure 5.9, is realized by routing. The border nodes act as routers that connect clusters and relay packets between the clusters. When a border node receives a packet, it examines the destination address, then forwards to the next border node in the adjacent cluster or to the destination node within the cluster. Only the DD can send a message to all the nodes within its network. The message is forwarded along the tree route of clusters. The border node should forward the broadcast packet from the
Network Topologies
Figure 2.1 shows 3 types of topologies that ZigBee supports: star topology, peer-to-peer topology and cluster tree.
1 Star Topology
In the star topology, the communication is established between devices and a single central controller,called the PAN coordinator. The PAN coordinator may be mains powered while the deviceswill most likely be battery powered. Applications that benefit from this topology include home automation, personal computer (PC) peripherals, toys and games. After an FFD is activated for the first time, it may establish its own network and become the PAN coordinator. Each start network chooses a PAN identifier, which is not currently used by any other network within the radio sphere of influence. This allows each star network to operate independently.
2 Peer-to-peer Topology
In peer-to-peer topology, there is also one PAN coordinator. In contrast to star topology, any device can communicate with any other device as long as they are in range of one another. A peer-to-peer network can be ad hoc, self-organizing and self-healing. Applications such as industrial control and monitoring, wireless sensor networks, asset and inventory tracking would benefit from such a topology. It also allows multiple hops to route messages from any device to any other device in the network. It can provide reliability by multipath routing.
3 Cluster-tree Topology
Cluster-tree network is a special case of a peer-to-peer network in which most devices are FFDs and an RFD may connect to a cluster-tree network as a leave node at the end of a branch. Any of the FFD can act as a coordinator and provide synchronization services to other devices and coordinators. Only one of these coordinators however is the PAN coordinator.
The PAN coordinator forms the first cluster by establishing itself as the cluster head (CLH) with a cluster identifier (CID) of zero, choosing an unused PAN identifier, and broadcasting beacon frames to neighboring devices. A candidate device receiving a beacon frame may request to join the network at the CLH. If the PAN coordinator permits the device to join, it will add this new device as a child device in its neighbor list. The newly joined device will add the CLH as its parent in its neighbor list and begin transmitting periodic beacons such that other candidate devices may then join the network at that device. Once application or network requirements are met, the PAN coordinator may instruct a device to become the CLH of a new cluster adjacent to the first one. The advantage of this clustered structure is the increased coverage area at the cost of increased message latency.
Figure 2.1 shows 3 types of topologies that ZigBee supports: star topology, peer-to-peer topology and cluster tree.
1 Star Topology
In the star topology, the communication is established between devices and a single central controller,called the PAN coordinator. The PAN coordinator may be mains powered while the deviceswill most likely be battery powered. Applications that benefit from this topology include home automation, personal computer (PC) peripherals, toys and games. After an FFD is activated for the first time, it may establish its own network and become the PAN coordinator. Each start network chooses a PAN identifier, which is not currently used by any other network within the radio sphere of influence. This allows each star network to operate independently.
2 Peer-to-peer Topology
In peer-to-peer topology, there is also one PAN coordinator. In contrast to star topology, any device can communicate with any other device as long as they are in range of one another. A peer-to-peer network can be ad hoc, self-organizing and self-healing. Applications such as industrial control and monitoring, wireless sensor networks, asset and inventory tracking would benefit from such a topology. It also allows multiple hops to route messages from any device to any other device in the network. It can provide reliability by multipath routing.
3 Cluster-tree Topology
Cluster-tree network is a special case of a peer-to-peer network in which most devices are FFDs and an RFD may connect to a cluster-tree network as a leave node at the end of a branch. Any of the FFD can act as a coordinator and provide synchronization services to other devices and coordinators. Only one of these coordinators however is the PAN coordinator.
The PAN coordinator forms the first cluster by establishing itself as the cluster head (CLH) with a cluster identifier (CID) of zero, choosing an unused PAN identifier, and broadcasting beacon frames to neighboring devices. A candidate device receiving a beacon frame may request to join the network at the CLH. If the PAN coordinator permits the device to join, it will add this new device as a child device in its neighbor list. The newly joined device will add the CLH as its parent in its neighbor list and begin transmitting periodic beacons such that other candidate devices may then join the network at that device. Once application or network requirements are met, the PAN coordinator may instruct a device to become the CLH of a new cluster adjacent to the first one. The advantage of this clustered structure is the increased coverage area at the cost of increased message latency.
Subscribe to:
Posts (Atom)
