Origins of Ad Hoc: Packet

Radio Networks
Sandeep Arora
SECE
LPU

Index
Introduction
Technical Challenges
Architecture of PRNETs
Components of Packet Radios
Routing in PRNETs
Route Calculation
Pacing Techniques
Media Access in PRNETs
Flow Acknowledgments in PRNETs
2

Introduction
Wireless Networking:

The term refers to any kind of networking that does

not involve cables.

It is a method by which homes,telecommunications

networksand enterprise (business) installations

avoid the costly process of introducing cables into a
building, or as a connection between various
equipment locations.

Wireless networks allow a mobile

telecommunications terminal to access the

wired information network infrastructures.

Wireless Network Setup :

Introduction
There are two types of wireless network types.
Infrastructure
Ad Hoc

Infrastructure

Also referred to as a hosted or managed

wireless network it consists of one or more
access points (know as gateways or wireless
routers) being connected to an existed network.
This will allow wireless devices to make use of
resources on the network such as printers and
the Internet.
4

Infrastructure Wireless
Network

Wireless Ad-hoc Network

Awireless ad-hoc networkis a decentralized

type ofwireless network.

The network is ad hoc because it does not rely on
a pre-existing infrastructure, such asroutersin
wired networks oraccess pointsin managed
(infrastructure)
wireless
networks.
Instead,
eachnodeparticipates in routing by forwarding
data for other nodes, and so the determination of
which nodes forward data is made dynamically
based on the network connectivity.
In addition to the classicrouting, ad hoc networks
can usefloodingfor forwarding the data.

Wireless Ad-Hoc Network

Also referred to as an unmanaged wireless

network it consists of each device connecting

directly to each other.
This will allow someone sitting outside with a

laptop to communicate with his desktop

computer in the house and access the Internet.
Once we have acquired the necessary wireless

networking hardware then the next step is to

connect it all together to form a network and
allow each device to communicate.
8

Differences to other wireless

networks

Mobile Ad Hoc Networks

(MANET)
Backbone
Mobile nodes
Access points

MANET
Wireless Mobile Network

10

Mobile Ad-hoc Network

Self-configuring network of mobile routers (and

associated hosts) connected by wireless links

This union forms a random topology
Routers move randomly free
Topology changes rapidly and unpredictably
Standalone fashion or connected to the larger
Internet
While MANETs are self contained, they can also
be tied to an IP-based global or local network
Hybrid MANETs
Suitable for emergency situations like natural
or human-induced disasters, military conflicts,
emergency medical situations, etc.
11

Fundamental Concepts
Ad hoc networks are autonomous networks

operating either in isolation or as stub

networks connecting to a fixed network
Do not necessarily rely on existing
infrastructure
No access point
Each node serves as a router and forwards
packets for other nodes in the network
Topology of the network continuously changes

12

Origin of Ad-Hoc Networks

Generic View of mobile ad hoc networks
First generation they were used for different military scenarios.
Packet radio networks was the first ad-hoc network system
Second generation from 1980s to the mid 1990s
Main aim were the same as for the first generation ad-hoc

networks system i.e. aiding combat/Battle operations.

Second generation developments focused on the further
advancement of the previously build ad-hoc network structure.
Some important developments ; Global mobile information
Systems, Near term Digital Radio (NTDR)
Third generation ad-hoc network systems are also known as
commercial ad-hoc network systems.
developments , Bluetooth ad-hoc sensor networks etc

13

First generation ad-hoc network

systems
The merits of having an infrastructure-less network were

discovered in the 1970s.

Defense Advanced Research Projects
Agency(DARPA) had a project known as packet radio,
where several wireless terminals could communicate with
one another on a battlefield.
DARPA initiated research on the feasibility of using
packet-switched radio communications to provide reliable
computer communications.
Packet radio was a technology that extended the
concept of packet switching (which evolved from point-topoint communication networks) to the domain of
broadcast radio networks.
Came up with packet radio network 1973-1987
14

 During the 1970s, the ALOHA ( Abramsons Logic Of

Hiring Access) project at the University of Hawaii

demonstrated the feasibility of using the broadcasting
property of radios to send/receive data packets in a
single radio hop system.
The ALOHA project later led to the development of a multihop multiple-access packet radio network (PRNET)
Unlike ALOHA, PRNET permits multi-hop
communications over a wide geographical area.
The DARPA PRNET has evolved through the years

(1973-1987) to be a robust, reliable, operational

experimental network.
The DARPA PRNET projects includes network devices,
routing protocols and protocols for automatic
distributed network management.
15

One of the most attractive features of PRNET is

rapid deployment. Once installed, the system
is self-initializing and self-organizing.
This implies that network nodes should be able
to discover radio connectivity among
neighboring nodes and organize routing
strategies based on this connectivity.
PRNETs are expected to require no system
administration and can be left unattended.

16

First generation ad-hoc network

systems
Packet radio network components
Firmware
Firmware can be loaded into a Packet Radio either locally (via

serial interface) or from the PRNET.

The firmware in each PR gathers information about bidirectional
link quality, nodal capacity and route characteristics and
provides this knowledge to debugging and monitoring
Communication
Use radio frequency technology to transmit and receive data
The implemented packet radios support omni-directional, spread

spectrum, half-duplex transmission and reception at 400kbit/s

and 100kbit/s rates
They implement the physical, data link and network layer (OSI
model).

17

Second generations ad-hoc

network systems
Started in 1980s -1993
Main Aim
Providing packet switched networking to the

mobile battlefield elements in infrastructureless environments.

Beneficial in improving
Radios performance by making them smaller,

cheaper and power-thrifty.

Scalability of algorithms
Resilience to the electronic attacks.

18

Second generations ad-hoc

network systems
GloMo (Global Mobile Information

Systems) project
Aim: to make the mobile environment user

friendly connectivity and access to services

for wireless mobile users.
Includes self organizing/self healing
networks; both flat and hierarchical multihop
routing algorithms

19

Second generations ad-hoc

network systems
Near Term Digital Radio Systems
The NTDR system is an experimental, mobile packet data

radio network.
The NTDR provides a self-organizing, self-healing, network

capability. Radio network management is provided by a

Network Management Terminal.
The

primary purpose of the NTDR is to provide data

transport for the Army Battle Command System automated
systems to units at brigade and below

Lessons learned from this experimental fielding provide a

portion of the technical baseline for radios being designed

for future fielding
20

Third generation mobile ad hoc

network system
1990s- onwards
Invention of notebook computers and viable

communication devices based on radio waves

concept of commercial ad-hoc networks has
arrived.
Idea of collection of mobile nodes were
purposed in research conferences
We see two main and important applications of
mobile ad-hoc networks
Bluetooth
Ad-hoc sensors
21

Technical Challenges
PRNETs are different from wired networks in many

aspects. They have an infrastructure-less backbone

and network nodes that act as routers or packet
switches to forward packets from one node to another.
Routers are connected without wires and routers
themselves can be mobile.
The introduction of wireless connectivity and the
presence of mobility result in great technical challenges
in the field of computer communications.
PRNET is the network that attempts to merge
computer communications with
telecommunications.
It allows networks to be formed and de-formed on-thefly, through a set of innovative and adaptive
communication protocols.
22

The technical challenges for PRNET can be

summarized as:
Flow control over a wireless multi-hop

communication route
Error control over wireless links
Deriving and maintaining network topology
information
Deriving accurate routing information
Mechanisms to handle router mobility
Shared channel access by multiple users
Processing capability of terminals
Size and power requirements
23

Network Architecture of PRNETs

24

Network Architecture of
PRNETs

PRNET consists of several mobile radio repeaters,

wireless terminals, and dedicated mobile stations.

The role of a repeater is to relay packets from one repeater
to another, until the packets eventually reach the
destination host. The mobile station is present to derive
routes from one host to another.
As network conditions change (terminal movement,
repeater failures or recovery, changes in hop reliability, and
network congestion state), routes are dynamically
reassigned by the station to satisfy minimum delay criteria.
Hosts and terminals attached to the PRNET are unaware of
the station's assignment and reassignment of
communication routes.
25

Components of Packet
Radios
user computer is interfaced to a radio via the terminal-network

controller (TNC).
user computer -> mobile device/terminal
radio and TNC logic ->packet radio

26

The packet radio, therefore, implements

functions related to protocol layers 1, 2,

and 3.
It is an intermediate system (IS) in the ISO
context.
A packet radio network (PRN) is a collection
of packet radios, with some packet radios
connected to user devices while others are
not.
27

Routing in PRNETs
Point-to-Point Routing
PRNETs support point-to-point communications through point-to-point
routing.
A packet originating at one part of the network moves through a
series of one or more repeaters until it eventually reaches the
final destination.
This point-to-point route is an ordered set of repeater addresses that is
determined by the mobile station.
The mobile station is the only element in the network that has
knowledge of the overall network connectivity, that is, the
network topology.
With network topology information, the mobile station computes the best
point-to-point route and distributes this information to all repeaters in the
route or directly to the source packet radio.
This scheme was found to be suitable for slow moving user terminals.
28

Broadcast Routing
Radio technology provides very good

broadcasting properties. Broadcasting

information to all radios in a network is
equivalent to flooding. To ensure that each
packet radio only forwards a packet once,
each repeater has to maintain a list of
packet identifiers for previously broadcast
packets that it recently had received and
forwarded.

29

 In broadcast routing, a packet radiates away from the source

packet radio in a wave-like fashion, that is, the packet ripples away
from the source.
Although broadcasting is very robust (since a packet will
be received by every node in the non-partitioned network),
it is not efficient for two-party communications since all other
nodes in the network must participate in the transmission and
reception of packets that are not intended for them.
Hence, when broadcast routing is used for point-to-point
communication, the destination host address is included in each
data packet. No specific routes are derived prior to data
transmission; hence, routing decisions are not centralized. Packets
will eventually reach the destination host if the network is not
partitioned. For fast moving user terminals, broadcast
routing was found to be useful as it avoids the need to process
rapidly changing routes.
30

Packet Forwarding
Impact of Mobility

31

Route Calculation
Neighbor table
Tier table
Device table

32

Neighbor Table
Broadcast a Packet Radio Organization Packet

(PROP) every 7.5 seconds

Announcing its existence and information about the

network topology from its own perspective at time.

Neighbors that hear a PROP make entry in their
neighbor tables
When nodes hears a PROP, it updates its neighbor
table
Transmitted data packets also used to build
neighbor table

Also tracks bidirectional quality of links with

neighbors (retransmission counts)

33

Neighbor Table
Neighboring PR

Link Quality

Node 1

3/9

Node 5

4/5

Node 7

6/9

Node 9

5/8

Link Quality
=

34

number of packets correctly received from the

transmitting packet radio during a PROP
number of packets that the transmitting packet radio
actually transmitted at that same interval

Tier Table
Routing in PRNETs relies on each packet radio

maintaining adequate knowledge of the best packet

radio to forward packets to for every prospective
destination.
The tier information ripples outward from each
packet radio at an average rate of 3.75 seconds per
hop and eventually reaches all packet radios.
Every packet radio knows its distance in tiers (or
radio hops) from itself to every prospective
destination and the next-hop packet radio.
This is, in principle, similar to the early ARPANET
routing algorithm which is based on the classical
Bellman-Ford routing.
35

Tier Table
Every packet radio knows the best next node on the route

from it to a given destination node

Tier 1 = 1 hop neighbors
These neighbors send out their PROPs indicating that they are
one hop from the originator
At next step, receivers of these PROPs know that they are 2
hops away from the originator
Process continues until every radio knows its distance in tiers
from every other radio
Best: shortest route with good connectivity on each hope
To change table, must discover a new node with better link
quality and lower tier number than currently recorded next
node
Also disseminate information about bad links in PROP messages

36

Tier Table

37

Destination PR

Next-Hop PR

Tier Count

Node 1

Node 7

Node 4

Node 4

Node 5

Node 8

Node 6

Node 3

Device Table

38

Each mobile device/terminal periodically sends a

control packet across the wired interface to its
attached packet radio.
Packet radio keeps track of affiliated devices and
propagates this mapping information via a PROP
to other packet radios in the network at an
average rate of 3.75 seconds per hop.
when a packet radio receives a packet
addressed to a specific mobile device, the
device currently attached to the packet radio is
known and the appropriate next hop-packet
radio is chosen to forward the packet.

Device Table
Logical addressing: maps device to a packet radio
Information about the radios attached device is included in

PROP messages
This allows new radios to be attached to devices and vice versa
Such correspondences are maintained in the device table at
each packet radio

PR Node
Device

Device
1

M
Q

39

Forwarding Protocols
Forwarding is accomplished via information read from the device and tier
tables and from the packet headers.
Unlike PROPs, user packets are not flooded to conserve available bandwidth
Packet Headers:
End-to-end header
The end-to-end header (ETE) is created by the source mobile
device/terminal, not the packet radio.
<Src Device ID, Dest Device ID, Type of Service Flag>
It includes the source device ID/address, which is used to update the

packet radio's device-to-packet radio mapping information, and the

destination device ID/address, which is used in packet forwarding.
The ETE header remains intact as the packet transits toward the
destination device.
ToS: indicate low latency/low reliability, e.g., speech

40

Routing header
In contrast to the ETE header, the routing header is

created by the source packet radio.

The routing header encapsulates the ETE header,
since it is the routing header that the packet radio will
use to forward the packets
<Src PR ID, Seq No, Speech ToS flag, Prev PR ID (for

acks), Prev PR transmission count, Transmitting PR

ID, Transmitting PR transmit count (for pacing), Next
PR ID, Lateral alternative routing flag, Alternative
routing request flag, Tier, Dest PR ID>
41

42

Forwarding Protocol
Device 1 --> Device 2 via PRs L, M, N
Device 1 --> PR L
Device sends packet PR L via its wired connection;

Prepare packet to forward on to PR N via PR M:

Dest PR ID <- N
Prev PR ID <- null
Trans PR ID <- L
Next PR ID <- M (known from tier table)
Tier <- 2 (from tier table)

PR Node
Device

Device
1
43

M
Q

Forwarding Protocol
PR L --> PR M
PR M receives packet over the air
Next PR ID = M, this PR should process the packet
Prepare to forward packet on to PR N:
Prev PR ID <- L
Transmitting PR ID <- M
Next PR ID <- N (known from tier table)
Tier <- 1 (from tier table)
Transmit packet to PR N and any other PR within range,

including L! This is an example of the passive

acknowledgement.
P PR Node
Device

Device
1
44

M
Q

Forwarding Protocol
PR M --> PR N
N receives packet, determines it should process it based on

Next PR ID
Determines that packet should be delivered to the attached
Device 2 (from ETE header and device table)
Sets in header, for the ack message:
P PR Node
Prev PR ID <- M
Trans PR ID <- N
Device
L
M
N
Next PR ID <- null
1
Tier <- null
Q
Ack message is sent, consisting only of header
Note that end PR cant use passive acknowledgement, so is
forced to transmit ack message to PR M
45

Device
2

Forwarding Protocol
Criteria for recognizing an Ack
Source PR ID and Seq No match the original

packet
AND must have arrived from further downstream:
Transmitting PR ID in ack packet is same as
next PR ID in original packet
Previous PR ID is same as receiving PRs ID--the
forward packet came from this packet radio
Ack packet contains a smaller tier number,
indicating it got closer to the destination PR

46

Forwarding Protocol
Retransmissions
If a packet is forwarded, and no ack is received,

the packet will be retransmitted after a time

out
Will do this six times before giving up
Interval between retransmission based on
pacing protocol, and grows with each
successive unsuccessful retransmission
At some point, sending PR assumes that it can
no longer reach the next radio on the hop and
sets its connectivity to that radio to 0

47

Forwarding Protocol
Alternative Routing
Alternative routing request flag
Receiving PR whose ID Next PR ID
This PR will forward if its tier table indicates it is less than

or equal to the tier in the header (it is as close or closer to

the destination than the sender)
Lateral Alternative Routing Flag is then set to insure that
the packet does not loop around at the same tier level for
ever--the next PR in the route MUST be closer to the
destination
Duplicate packets filtered out by checking Source PR ID and
sequence number field (i.e., Unique Packet ID--UPI)
When detected at receiver, will actively ACK sender to
squelch retransmissions of duplicate packet

48

Transmission Protocols
Pacing protocol
Provide Flow and congestion control mechanisms
The time at which a packet is selected for

transmission is determined by a three-component

packing protocol.
Transmission parameters are chosen based on
measure link quality and the type of service
desired by the user.
Also promotes fair use of the radio spectrum
Single Threading
Forwarding Delay Measurement
Measurement of Retransmissions

49

50

Transmission Protocols
Single Threading
Last packet sent to PR must be ackd or discarded before next packet

is sent to the same PR

Passive acks imply that next hop PR now ready to accept a new
packet
Deflects congestion bottleneck away from source PR
Limitation : two buffer allocated per packet radio for packet received
over the wired interface for entry into the PRNET
Forwarding Delay

packet radio records the time at which its transmission completes and
when it receives the acknowledgment from the next packet radio. This
difference is known as forwarding delay
Affects the setting of retransmission intervals
Includes processing, queing, carrier sense/random access,
transmission delay from neighboring PR
Exponentially smoothed to get short term history of delay likely to be
valid in next transmit/ack cycle
51

Media Access in PRNETs

PRNETs employ the Carrier Sense Multiple Access

(CSMA) protocol to coordinate communications among

mobile hosts.
CSMA prevents a packet radio from transmitting at the
same time when a neighboring packet radio is using
the medium.
A packet radio is aware if a neighbor is transmitting
by reading its hardware indication bit-synchronizationin-the-lock.
Basically, this bit, when set, implies that the channel
is busy and a carrier is being sensed.
Whenever a carrier is being sensed, a packet radio
will refrain from transmitting.
52

CSMA
Carrier Sense Multiple Access(CSMA) is aprobabilisticMedia Access

Control(MAC) protocol in which a node verifies the absence of

othertrafficbeforetransmittingon a sharedtransmission medium,
such as an electrical bus, or a band of theelectromagnetic spectrum.
"Carrier Sense" describes the fact that
atransmitterusesfeedbackfrom a receiver that detects acarrier
wavebefore trying to send. That is, it tries to detect the presence of
an encodedsignalfrom another station before attempting to transmit.
If a carrier is sensed, the station waits for the transmission in progress
to finish before initiating its own transmission. In other words, CSMA is
based on the principle "sense before transmit" or "listen before talk".
"Multiple Access" describes the fact that multiple stations send and
receive on the medium. Transmissions by one node are generally
received by all other stations using the medium.

53

While carrier sensing reduces the

probability of channel contention, it cannot

eliminate hidden terminal and exposed
nodes problems.
The former is a result of a node lying within
the radio range of the receiver, but not
another transmitter that is two hops away.
The latter results in neighboring nodes of a
transmitter being blocked from
transmission.
54

Flow Acknowledgments in
PRNETs
Packets are forwarded via a single

communication route through a PRNET.

Each packet radio must
examines the information contained in the

packet headers and in its own device and tier

tables.
decide if it should be the one to transmit the
packet, if it should update the routing header
before transmitting, and if it should update
its own tables.

55

56

 Other packet radios within the radio range will also each

receive the transmitted packet.

If these neigbors are not part of the route, they will
discard the overheard packets.
The downstream node that receives the packet will
process the packet and proceed with issuing a passive
acknowledgment.
The single transmission, therefore, not only forwards the
packet on to the next packet radio but also
acknowledges the previous packet radio that the packet
was successfully received and is being forwarded. This
principle of passive acknowledgment will proceed
until the packet reaches the destination node. reception
of the packet.
57

Since the destination node does not

have a downstream node and it is the

terminating point, an active
acknowledgment is sent by the
destination node to its upstream node to
confirm successful

58