Python代写:CS420 WSNn Project




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.

  1. Root Node
  2. Cluster Head
  3. Router
  4. 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.


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.


  • 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.

  1. 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.
  2. 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.
  3. Develop a protocol to move the cluster head role between nodes.
  4. Sensor node, sampling and transmitting data to the root at predefined intervals
  5. 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.
  6. 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.
  7. 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.
  8. 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.
  9. 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