Collection Tree Protocol

Last updated

The Collection Tree Protocol (CTP) is a routing protocol for wireless sensor networks. It is used for transferring data from one or more sensors to one or more root nodes.

A routing protocol specifies how routers communicate with each other, distributing information that enables them to select routes between any two nodes on a computer network. Routers perform the "traffic directing" functions on the Internet; data packets are forwarded through the networks of the internet from router to router until they reach their destination computer. Routing algorithms determine the specific choice of route. Each router has a prior knowledge only of networks attached to it directly. A routing protocol shares this information first among immediate neighbors, and then throughout the network. This way, routers gain knowledge of the topology of the network. The ability of routing protocols to dynamically adjust to changing conditions such as disabled data lines and computers and route data around obstructions is what gives the Internet its survivability and reliability.

Contents

Algorithm

The number of expected transmissions needed to send data between two nodes, ETX, is used as the routing metric. This assumes packets are retransmitted at the link layer. Routes with a lower metric are preferred. In a route that includes multiple hops, the metric is the sum of the ETX of the individual hops.

The ETX metric, or expected transmission count, is a measure of the quality of a path between two nodes in a wireless packet data network. It is used extensively in mesh networking algorithms.

In computer networking, the link layer is the lowest layer in the Internet Protocol Suite, the networking architecture of the Internet. It is described in RFC 1122 and RFC 1123. The link layer is the group of methods and communications protocols that only operate on the link that a host is physically connected to. The link is the physical and logical network component used to interconnect hosts or nodes in the network and a link protocol is a suite of methods and standards that operate only between adjacent network nodes of a local area network segment or a wide area network connection.

Each node that wishes to collect data advertises itself as a tree root. Each node sends its data to the tree root to which it is nearest, that is, the tree root from which it is separated by the smallest ETX. A tree root always has an ETX of zero.

Each node only keeps the smallest ETX (to the nearest tree root). The collection of ETX values is known as a gradient, and messages are only sent down the gradient from nodes with higher ETX to nodes with smaller ETX. This kind of forwarding is common to many algorithms and protocols in wireless sensor networks.

Rapidly changing link qualities, for example in sensor networks with moving nodes, cause routing information to become outdated which can lead to routing loops. CTP attempts to address these issues through datapath validation and adaptive beaconing.

Datapath validation

Each packet contains the ETX from the sender to the root. If a node receives a packet with ETX lower than its own this indicates an inconsistency in the tree. This triggers the transmission of a beacon frame. The goal is to have the sender of the packet receive the beacon frame and adjust its ETX accordingly.

Adaptive beaconing

The interval with which nodes broadcast beacons presents a tradeoff. If beacons were sent more frequently the routing information would be up to date more often and the network would respond to changes in topology faster. However, sending beacons more frequently leaves less bandwidth for application level data and uses more energy. To get around this CTP uses adaptive beaconing. It sends beacons faster when it detects problems. If it doesn't detect problems it exponentially decreases the beacon sending rate.

An application layer is an abstraction layer that specifies the shared communications protocols and interface methods used by hosts in a communications network. The application layer abstraction is used in both of the standard models of computer networking: the Internet Protocol Suite (TCP/IP) and the OSI model. Although both models use the same term for their respective highest level layer, the detailed definitions and purposes are different.

Related Research Articles

Internetwork Packet Exchange (IPX) is the network layer protocol in the IPX/SPX protocol suite. IPX is derived from Xerox Network Systems' IDP. It may act as a transport layer protocol as well.

The Transmission Control Protocol (TCP) is one of the main protocols of the Internet protocol suite. It originated in the initial network implementation in which it complemented the Internet Protocol (IP). Therefore, the entire suite is commonly referred to as TCP/IP. TCP provides reliable, ordered, and error-checked delivery of a stream of octets (bytes) between applications running on hosts communicating via an IP network. Major internet applications such as the World Wide Web, email, remote administration, and file transfer rely on TCP. Applications that do not require reliable data stream service may use the User Datagram Protocol (UDP), which provides a connectionless datagram service that emphasizes reduced latency over reliability.

A virtual circuit (VC) is a means of transporting data over a packet switched computer network in such a way that it appears as though there is a dedicated physical layer link between the source and destination end systems of this data. The term virtual circuit is synonymous with virtual connection and virtual channel. Before a connection or virtual circuit may be used, it has to be established, between two or more nodes or software applications, by configuring the relevant parts of the interconnecting network. After that, a bit stream or byte stream may be delivered between the nodes; hence, a virtual circuit protocol allows higher level protocols to avoid dealing with the division of data into segments, packets, or frames.

In computer networking a routing table, or routing information base (RIB), is a data table stored in a router or a networked computer that lists the routes to particular network destinations, and in some cases, metrics (distances) associated with those routes. The routing table contains information about the topology of the network immediately around it. The construction of routing tables is the primary goal of routing protocols. Static routes are entries made in a routing table by non-automatic means and which are fixed rather than being the result of some network topology "discovery" procedure.

In computer networking, the transport layer is a conceptual division of methods in the layered architecture of protocols in the network stack in the Internet protocol suite and the OSI model. The protocols of this layer provide host-to-host communication services for applications. It provides services such as connection-oriented communication, reliability, flow control, and multiplexing.

Anycast Network addressing and routing methodology

Anycast is a network addressing and routing methodology in which a single destination address has multiple routing paths to two or more endpoint destinations. Routers will select the desired path on the basis of number of hops, distance, lowest cost, latency measurements or based on the least congested route. Anycast networks are widely used for content delivery network (CDN) products to bring their content closer to the end user.

The Resource Reservation Protocol (RSVP) is a transport layer protocol designed to reserve resources across a network for quality of service (QoS) using the integrated services model. RSVP operates over an IPv4 or IPv6 and provides receiver-initiated setup of resource reservations for multicast or unicast data flows. It does not transport application data but is similar to a control protocol, like Internet Control Message Protocol (ICMP) or Internet Group Management Protocol (IGMP). RSVP is described in RFC 2205.

Protocol Independent Multicast Internet protocol

Protocol-Independent Multicast (PIM) is a family of multicast routing protocols for Internet Protocol (IP) networks that provide one-to-many and many-to-many distribution of data over a LAN, WAN or the Internet. It is termed protocol-independent because PIM does not include its own topology discovery mechanism, but instead uses routing information supplied by other routing protocols. PIM is not dependent on a specific unicast routing protocol; it can make use of any unicast routing protocol in use on the network. PIM does not build its own routing tables. PIM uses the unicast routing table for reverse path forwarding.

In computer network research, network simulation is a technique whereby a software program models the behavior of a network by calculating the interaction between the different network entities. Most simulators use discrete event simulation - the modeling of systems in which state variables change at discrete points in time. The behavior of the network and the various applications and services it supports can then be observed in a test lab; various attributes of the environment can also be modified in a controlled manner to assess how the network / protocols would behave under different conditions.

IP multicast is a method of sending Internet Protocol (IP) datagrams to a group of interested receivers in a single transmission. It is the IP-specific form of multicast and is used for streaming media and other network applications. It uses specially reserved multicast address blocks in IPv4 and IPv6.

TCP tuning techniques adjust the network congestion avoidance parameters of Transmission Control Protocol (TCP) connections over high-bandwidth, high-latency networks. Well-tuned networks can perform up to 10 times faster in some cases. However, blindly following instructions without understanding their real consequences can hurt performance as well.

Packet loss occurs when one or more packets of data travelling across a computer network fail to reach their destination. Packet loss is either caused by errors in data transmission, typically across wireless networks, or network congestion. Packet loss is measured as a percentage of packets lost with respect to packets sent.

Flooding (computer networking) Simple routing algorithm sending incoming packets to all other links than the sender

Flooding is a simple computer network routing algorithm in which every incoming packet is sent through every outgoing link except the one it arrived on.

The B protocol, or CIS B, is a file transfer protocol developed for the CompuServe Information Service, and implemented in 1981. The protocol was later expanded in the QuickB version and later the enhanced B Plus version. It was a fairly advanced protocol for its era, supporting efficient transfers of files, commands and other data as well, and could be used in both directions at the same time in certain modes. These advanced features were not widely used, but could be found in a small number of client-side packages.

Pastry is an overlay network and routing network for the implementation of a distributed hash table (DHT) similar to Chord. The key-value pairs are stored in a redundant peer-to-peer network of connected Internet hosts. The protocol is bootstrapped by supplying it with the IP address of a peer already in the network and from then on via the routing table which is dynamically built and repaired. It is claimed that because of its redundant and decentralized nature there is no single point of failure and any single node can leave the network at any time without warning and with little or no chance of data loss. The protocol is also capable of using a routing metric supplied by an outside program, such as ping or traceroute, to determine the best routes to store in its routing table.

Roofnet was an experimental 802.11b/g mesh network developed by the Computer Science and Artificial Intelligence Laboratory at the Massachusetts Institute of Technology (MIT). Research included link-level measurements of 802.11, finding high-throughput routes in the face of lossy links, link adaptation, and developing new protocols which take advantage of radio’s unique properties (ExOR). The software developed for this project is available free as open source.

A wireless ad hoc network (WANET) or MANET is a decentralised type of wireless network. The network is ad hoc because it does not rely on a pre-existing infrastructure, such as routers in wired networks or access points in managed (infrastructure) wireless networks. Instead, each node participates in routing by forwarding data for other nodes, so the determination of which nodes forward data is made dynamically on the basis of network connectivity and the routing algorithm in use.
In the Windows operating system, ad-hoc is a communication mode (setting) that allows computers to directly communicate with each other without a router.
Wireless mobile ad hoc networks are self-configuring, dynamic networks in which nodes are free to move. Wireless networks lack the complexities of infrastructure setup and administration, enabling devices to create and join networks "on the fly" – anywhere, anytime.

A mobile wireless sensor network (MWSN) can simply be defined as a wireless sensor network (WSN) in which the sensor nodes are mobile. MWSNs are a smaller, emerging field of research in contrast to their well-established predecessor. MWSNs are much more versatile than static sensor networks as they can be deployed in any scenario and cope with rapid topology changes. However, many of their applications are similar, such as environment monitoring or surveillance. Commonly, the nodes consist of a radio transceiver and a microcontroller powered by a battery, as well as some kind of sensor for detecting light, heat, humidity, temperature, etc.

References

CiteSeerx is a public search engine and digital library for scientific and academic papers, primarily in the fields of computer and information science. CiteSeer holds a United States patent # 6289342, titled "Autonomous citation indexing and literature browsing using citation context," granted on September 11, 2001. Stephen R. Lawrence, C. Lee Giles, Kurt D. Bollacker are the inventors of this patent assigned to NEC Laboratories America, Inc. This patent was filed on May 20, 1998, which has its roots (Priority) to January 5, 1998. A continuation patent was also granted to the same inventors and also assigned to NEC Labs on this invention i.e. US Patent # 6738780 granted on May 18, 2004 and was filed on May 16, 2001. CiteSeer is considered as a predecessor of academic search tools such as Google Scholar and Microsoft Academic Search. CiteSeer-like engines and archives usually only harvest documents from publicly available websites and do not crawl publisher websites. For this reason, authors whose documents are freely available are more likely to be represented in the index.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.