A Tutorial of 802.11 Implementation in ns-2
Yue Wang
MobiTec Lab, CUHK
1. Introduction to ns-2
1.1 ns-2
Ns-2 [1] is a packet-level simulator and essentially a centric discrete event scheduler to schedule
the events such as packet and timer expiration. Centric event scheduler cannot accurately emulate
“events handled at the same time” in real world, that is, events are handled one by one. However,
this is not a serious problem in most network simulations, because the events here are often
transitory. Beyond the event scheduler, ns-2 implements a variety of network components and
protocols. Notably, the wireless extension, derived from CMU Monarch Project [2], has 2
assumptions simplifying the physical world:
(1) Nodes do not move significantly over the length of time they transmit or receive a packet.
This assumption holds only for mobile nodes of high-rate and low-speed. Consider a node with the
sending rate of 10Kbps and moving speed of 10m/s, during its receiving a packet of 1500B, the
node moves 12m. Thus, the surrounding can change significantly and cause reception failure.
(2) Node velocity is insignificant compared to the speed of light. In particular, none of the
provided propagation models include Doppler effects, although they could.
1.2 GloMoSim
GloMoSim [3] is another open-source network simulator based on a parallel discrete event
scheduler. Hopefully, it can emulate the real world more accurately. However, it is hard to debug
parallel programs. Although GloMoSim currently only supports pure wireless networks, it
provides more physical-layer models than ns-2, as shown in Table 1 [4].
Table 1. Physical layer and propagation models available in GloMoSim, ns-2 and OPNET
1.3 Ns-2 Basics
Ns-2 directory structure
As shown in Figure 1, the C++ classes of ns-2 network components or protocols are implemented
in the subdirectory “ns-2”, and the TCL library (corresponding to configurations of these C++
instances) in the subdirectory of “tcl”.
Figure 1. Ns-2 directory structure
Network Components
Network components are Node, Link, Queue, etc. Some of them are simple components, that is,
they are created from the corresponding C++ classes; The other are compound components, that is,
they are composed multiple simple C++ classes, e.g. Link are composed of Delay (emulating
propagation delay) and Queue. In general, in ns-2, all network components are created, plugged
and configured from TCL.
Example: Plug MAC into NetIF (Network Interface)
Class MAC {
void send (Packet* p);
void recv(Packet*, Handler* h);
NsObject* target_ //an instance of NetIF
}
Event Scheduling
Events are something associated with time. class Event is defined by {time, uid, next, handler},
where time is the scheduling time of the event, uid is the unique id of the event, next is the next
scheduling event in the event queue that is a linklist, and handler points to the function to handle
the event when the event is scheduled. Events are put into the event queue sorted by their time,
and scheduled one by one by the event scheduler. Note that class Packet is subclass of class Event
as packets are received and transmitted at some time. And all network components are subclass of
class Handler as they need to handle events such as packets.
The scheduling procedure (void Scheduler::schedule(Handler* h, Event* e, double delay)) is
shown in Figure 2. The event at the head of the event queue is delivered to its hander of some
network object. Then, this network object may call other network object, and finally some new
events are inserted into the event queue.
Figure 2. Discrete Event Scheduler
Example: A and B are two mobile nodes. And A sends packet p to B (suppose they are within the
tx range).
A::send (Packet* p) {target_->recv(p)} //target_ is B; call B::recv
B::recv(Packet*, Handler* h = 0) {
…
Scheduler::instance().schedule(target_, p, tx_time) //target_ is B; schedule the packet at the
// time of (current_time + tx_time)
…
}
Example: Timer is another kind of Event that is handled by TimerHandler
class TimerHandler: public Handler
expire (Event *e) //the virtual handling function overloading by users
resched(double delay) //the time expires at the time of (current_time + delay)
handle(Event *e){
}
Note: In ns, NO REAL time, timer, recv, send and packet flows in the sense of UNIX network
programming.
2. 802.11 Implementation
2.1 Physical Layer
Figure 3 Schematic of a mobile node under the CMU Monarch wireless extensions to ns.
Figure 3 shows the network components in the mobile node and the data path of sending and
receiving packets. In this section, we describe the basic function of the physical layer and MAC is
detailed in the next section.
Channel (channel.cc)
The function of class Channel is to deliver packets from a wireless node to its neighbors within the
sensing range.
I. Stamp txinfo in the packets before sending:
p->txinfo_.stamp((MobileNode*)node(), ant_->copy(), Pt_, lambda_)
Note: Here node() are the pointer of the sending node, ant_->copy() is the antenna’s parameters
such as the height of the antenna, Pt_ is the transmitting power, and lamba_ is the wavelength of
light. These information is used for the receiving node to calculate the receiving power.
II. Send packets to the nodes within the sensing range distCST_ to be sensed or received by
these nodes.
distCST_ = wifp->getDist(wifp->getCSThresh(), wifp->getPt(), 1.0, 1.0,
highestZ , highestZ, wifp->getL(), wifp->getLambda());
Note: distCST is calculated by the parameters such as CS Threshold, transmission power, antenna
gains, antenna heights, system loss factor, and wavelength of light.
NetIF (wireless-phy.cc)
The function of class WirelessPhy is to send packets to Channel and receive packet from Channel.
I. Packet Sending
channel_->recv(p, this);
II. Packet Reception, sendUp()
//calculate Rx power by path loss models
Pr = propagation_->Pr(&p->txinfo_, &s, this)
pkt_recvd = 1;
hdr->error = 1; // error reception, for Carrier Sense
pkt_recvd = 0; // cannot hear it
if (Pr < CSThresh_) {
…
}
if (Pr >= CSThresh_ && Pr < RXThresh_){
…
}
if (Pr >= RXThresh_) {
…
}
pkt_recvd = 1;
hdr->error = 0; // maybe correct reception
Note: First, ns-2 calculates the receiving power Pr by the tx_info_ of p and the receiver this. When
Pr is less than CSThresh_ (Carrier Sense Threshold), the receiver cannot sense it; else, the receiver
can sense it and even receive it without error in the case that Pr > RXThresh_ (Reception
Threshold, and RXThresh_ > CSThresh_). Besides, successful reception also depends on the
packet’s SIR is larger than CPThresh_ (Capture Threshold), which is checked in MAC layer.
2.2 MAC
MAC (mac-802_11.cc)
The function of class Mac802_11 has 2 functions. On sending, it uses CSMA/CA medium access
mechanism; On receiving, it adopts SIRT (SIR Threshold) based reception (Capture).
State Transition Diagram
Figure 4. 802.11 MAC state transition diagram
State transition diagram can help us write or read network programs. Thus, before analyzing
802.11 source codes in ns-2, we first show the reference 802.11 MAC state transition diagram [5]
in Figure 4 that is somewhat different with ns-2. First, we need to find out the basic states.
= 0x0200,
= 0x0400,
= 0x0800,
Elementary States
enum MacState {
MAC_IDLE = 0x0000,
MAC_POLLING = 0x0001, // ns 802.11 does not implement Polling
MAC_RECV = 0x0010,
MAC_SEND = 0x0100,
MAC_RTS
MAC_CTS
MAC_ACK
MAC_COLL = 0x1000
};
MacState
MacState tx_state_//can be MAC_IDLE, MAC_SEND, MAC_RTS, MAT_CTS, MAC_ACK
double
//channel is idle
int is_idle() {
if (tx_state_ == MAC_IDLE && rx_state_ == MAC_IDLE
rx_state_ //can be MAC_IDLE, MAC_RECV, MAC_COLL
nav_ //expiration of Network Allocation Vector
&& nav_ <= NOW)
return 1;
else
return 0;
}
Note: The above is_idle() check whether the channel is idle at the moment when it is called.
MAC Timers
Timers are very important in 802.11 in triggering channel access. The following shows the basic
timers and their functions.
BackoffTimer mhBackoff_
void start(int cw, int idle);// if is_idle(), start to count down; else freeze the timer
void pause(); //freeze the timer when the
void resume(double difs);//resume to count down after DIFS
void handle(Event *); //send RTS or DATA after it times out
int busy(); //Is counting down
DeferTimer mhDefer_
void start(double defer);//start to count down
void handle (Event *);//eg. send CTS or ACK after SIFS expires
int busy(); //Is counting down
IFTimer
NavTimer
RxTimer
TxTimer
Recv/Send functions
mhIF_;
mhNav_;
mhRecv_;
mhSend_;
// interface timer, set interface state active when transmitting
// NAV timer
//completion of incoming packets, call recvHandler()
//sending timeout (e.g. no ACK received), call sendHandler()
void setTxState (MacState newState) //For tx_state_
void setRxState (MacState newState)//For rx_state_
void checkBackoffTimer() {
}
mhBackoff_.resume(phymib_.getDIFS());
if(is_idle() && mhBackoff_.paused())
if(! is_idle() && mhBackoff_.busy() && ! mhBackoff_.paused())
mhBackoff_.pause();
}
mhNav_.stop();//reset nav_
double now = Scheduler::instance().clock();
double t = us * 1e-6;
if((now + t) > nav_) {
nav_ = now + t;
if(mhNav_.busy())
mhNav_.start(t);
}
Note: the above sample codes show how receiving and sending will change MAC state and further
control the backoff timer.
/* Note: nav_ expires also mean channel is idle, then call mhBackoff_resume() */
void set_nav(u_int16_t us) {
Note: NAV timer is set by RTS or CTS to indicate the residual time of data transmission. However,
it is extended in ns-2 to also reflect the residual time before channel becomes idle, and thus can
replace the function of carrier sense. The usage is, update the NAV timer with the transmission
time of either received packets or sensed packets, set_nav (txtime(p)). When NAV timer expires,
navHandler() is called to resume backoff timer.
CSMA/CA
recv function is generally the entry of most network protocols (handling packets from both uplayer
and downlayer). For outgoing packets, it will call send function that is the entry of CSMA/CA.