数据采集是无线传感器网络 [ WSN ](https://www.geeksforgeeks.org/wireless-sensor-network-
wsn/ “WSN”) 和物联网 [ IoT ](https://www.ibm.com/blogs/internet-of-things/what-is-
the-iot/ “IoT”) 的重要应用，完成分层数据收集树的设计和实现。
Requirement
Data collection is an important application of wireless sensor networks (WSNs)
and Internet of Things (IoT). During the semester, we have initiated the
design and implementation of a hierarchical data collection tree where sensor
nodes are arranged at different levels for transmitting data to a sink node we
called root node.
The data collection tree developed during the class is organized into clusters
in a multihop architecture as shown in Figure 1.
At the root of the network is a node identified as root node serves as the
controller for the entire network. The root node is also the clusterhead for
network 1 which is the root network. Each network in this topology is managed
by a clusterhead which serves as the router for the nodes in its cluster. In
addition, the clusterhead is the manager for its own cluster. Clusterheads
form a backbone network such as the one given in Figure 2.
There are four roles in this network.
- Root Node
- Cluster Head
- Router
- Node
The Root node is responsible for the management of the entire network,
creation of new clusters and maintaining network topology. It is also
responsible for acting as a gateway between the data collection tree and
external networks such as IP networks. By definition root node will have more
than one network interface to be able to act as a router/gateway between data
collection tree and external networks.
The Cluster Head is responsible to admission of new nodes into the network and
assigning local network addresses. Cluster heads also serves as a router
between the nodes in its network and the root as well as other clusters.
Router is a functionality that will be performed by clusterheads and other
designated roles. Routers repeat the packets they received towards their
destination.
Nodes are sensor or actuator nodes that does not have additional network
functions.
Addressing
Each node will have a globally unique ID (GUID) assigned to the node at the
time of production. The GUID be used for identification of individual nodes.
For routing and communication purposes the network will utilize dynamically
assigned addresses. The addresses will be two byte short addresses and will be
composed of two parts (NetworkID, NodeID). Network ID will identify the
cluster to which nodes belong to and NodeID will identify nodes within a
cluster.
The following addresses are predefined:
- 2 - bytes (Network ID + Node ID) (8 bits each)
- 0.X - reserved
- 254.X - multicast
- X.254 - cluster heads
- 255.255 - broadcast
- X.255 - local broadcast
- 255.X - reserved
Node Attributes and Roles
Based on the capabilities of the node (battery, transceiver, processor or
policy related) each node may have a number of attributes as defined below.
Some of these attributes will be assigned at the time the node is produced (is
root eligible for example). The attributes such as “is root eligible” and “is
router eligible” will be used during the network setup and runtime to decide
the role of a network. These attributes will take a true/false value and will
not be changed during the runtime.
- Node type
- IsRouter?
- IsRegistered?
- IsRoot?
- IsGateway?
- IsRouterEligible?
- IsRootEligible?
- IsaddressAssigned?
The attributes such as “Is Router”, “Is Root “ are assigned at run time and
will identify the role of the node in the network. Initially all nodes will be
initialized to the following attribute values ( the run time assigned
attributes). - IsRouter = False
- IsRegistered = False
- IsRoot = False
- IsGateway = False
- IsaddressAssigned = False
Common Packet Header
The network will use the following common packet header.
CommonHeader
- NextHop : 2 bytes
- DestinationAddress : 2 bytes
- SourceAddress : 2 bytes
- PacketType : 1 byte
- Payload : N bytes
Initialization of the Network
When a sensor node is powered on it will start listening to the channel (if
there are more than one possible channel it will listen on all available
channels to determine whether a network exists or not. Depending on the node
attributes ( IsRootEligible and IsRouterEligible) and the availability of a
network the role and behavior of the network will be determined. The activity
of a node arriving to a channel is given in Figure 1.
As shown in the SDL (Specification and Description Language) diagram in Figure
1, the node arriving to the channel will set a trial counter of N to zero and
start a timer (Timer A). It will them start listening to the channel for
potential network activity. There are two potential events that will activate
the node. The Timer A may expire indicating no network activity during the
listening period. In this case , the number of listening attempts (N) will be
compared to a preestablished threshold and if the number of attempts is less
then the threshold Timer A will be restarted and number of attempts N will be
incremented by one. If the number of attempts N is larger than the threshold,
the action of the node depends on the node abilities. If this node is
rootEligible than the node will claim the role of the root node. If the node
is not root eligible than it will set a time B ( which will presumably longer
than Timer A) and will go into a sleep mode. During the sleep mode. The node
will come out of sleep mode when time B expires and will rerun the node search
model we explained here.
If a packet arrives during the channel listening, the node will check if this
is a heartbeat packet and decide next action based whether the packet is a
heartbeat packet. A heartbeat packet will be transmitted by root node and
clusterheads to indicate availability of the network and the willingness of
accepting new nodes into the network. If the packet is a heartbeat packet the
node will initiate the network join process, otherwise the packet will be
ignored as shown in Figure 1.
The node that becomes root will also assume the role of the clusterhead for
network 1.
The protocol defined in Figure 1, specifies two timers and two packets
(Heartbeat message and Probe packet without going into details of these two
packets. The probe packet is intended to force response from clusterheads and
the response to the probe will in this case be a heartbeat message. All
messages transmitted on this network will be transmitted using a common header
described before.
Several components of this network has been designed in class. SDL diagrams
and sequence diagrams have been discussed for various design options. In
addition, a python simulation model has been developed for the network design.
You are expected to develop a report of the network design by providing an SDL
diagram, a sequence diagram and a description of the node activity. In
addition, you will be responsible for mapping each activity diagram to the
model code in python and make necessary updates to the network model. In the
following pages please provide the design of the algorithms for the following
cases.
- Join a cluster, address assignment by the cluster head. a. Provide the SDL diagram for both the cluster head and the node b. Provide a sequence diagram showing the interaction between the new node and cluster head. c. Describe all packets exchanged, suggest the packet content by detailing each field.
- Create a new cluster, network ID assignment by the cluster head. Will be triggered by a node outside the radio distance of a cluster head. Please to design two algorithms for the two variations below. For each case provide SDL diagrams and sequence diagrams clearly indicating the role of the node on the timeline of the algorithm (in sequence diagram)
* a. The cluster head of the new cluster will be a node in the existing cluster. The new node joining the network will be a member of the new cluster created.
* b. The cluster head of the new cluster will be the node joining the network. This solution is expected to reduce the cluster overlap.
* c. Describe all packets exchanged, suggest the packet content by detailing each field. - Develop a protocol to move the cluster head role between nodes.
- Sensor node, sampling and transmitting data to the root at predefined intervals
- Recovery from Node and Link Failures
* a. Discuss the process and protocol elements (provide SDL and other relevant diagrams) for determine node and link failures
* b. Discuss recovery from node and link failures by using a minimum two different algorithms. For both algorithms define the SDL diagrams, sequence diagrams and provide a discussion of the algorithms. - In case of node and link failures, network nodes will move from one cluster to the next. With this move their dynamically assigned addresses will be updated. The addresses that are used for routing and all messaging activity are the dynamically assigned addresses. I believe there is a need to design a name resolution protocol for mapping globally unique IDs to dynamically assigned addresses to make sure that the messages addressed to a particular node indeed are delivered to that node. Discuss the address resolution in case of node and link failures and offer an algorithm.
- Develop an overlay multicast protocol on the network designed. The multicast address range is identified earlier. Discuss the implementation of the multicast protocol in our modeling and simulation platform. Provide code examples and updated code with relevant sections updated to reflect your multicast protocol.
- For all nodes (discuss how routing tables are created, how are they updated and map routing activity to the routing table clearly demonstrating routing activity in the network.
- Describe all packets and all fields in all packets. Explain why a particular field exists, defaults values for the field, valid ranges for each field.
The diagrams in this assignment are drawn by visio and SDL template is used.
Several of the components asked here in this report has been already designed
in class. For those designs you will need to properly document the protocol in
the report. For the protocol components that are not yet implemented, you are
expected to design and document the protocol elements
