Models

A system that can be modeled is not the system itself. 
A model that can be made is not the absolute model. 
That which has no model is the origin of a system. 
That which has a model is the understanding of the system.

--- Zhang Ying

Introduction:

The current version of Prowler provides three radio models and a MAC layer simulating that of the Berkeley motes. We will describe the simplest probabilistic radio model among the three, the default radio model in Prowler. For other radio models, please check out references on the Prowler web site.

Rmase, in addition, provides a topology model, an application model, and a performance model.

Radio/MAC Model:

A radio propagation model determines the strength of a transmitted signal at a particular point of the space for all transmitters in the system. Based on this information, the signal reception conditions for the receivers can be evaluated and collisions can be detected. A simple transmission model is given by:


P_{rec, ideal}(d) ¬ P_transmit / (1+d^γ),  where  2 £  γ  £ 4
P_rec(i, j) ¬ P_{rec, ideal}(d_i,j)(1+α(i,j))(1+β(t))

where P_transmit is the signal strength at the sender and P_{rec, ideal}(d) is the ideal received signal strength at distance d, α and β are random variables with normal distributions N(0, σ_α) and N(0, σ_β), respectively. A network is  asymmetric if σ_α>0 or σ_β >0. In this model, α is static depending on locations i and j only, and β is dynamic, changing over time. Furthermore, an additional parameter p_error models the probability of a transmission error by any un-modeled effects.
 

A simple signal reception model is that the signal is received if the signal strength is greater than a reception threshold. A node j can receive a packet from node i if P_rec(i, j) > D where D is the threshold. There is a collision if two transmissions overlap in time and both could be received.

 

A more complicated transmission model, Rayleigh fading model, and a more complicated reception and collision model, considering the signal to interference and noise ratio (SINR) for each receiver and transmitter pair, are also available in Prowler, which are computationally more expensive.
 

The MAC layer in Prowler simulates the Berkeley motes'  CSMA MAC protocol,  with a random waiting time, idle channel checking, and a random back-off interval, for sending a packet in the air.

 

Name	Explanation	Typical Values
Radio model (γ, σα , σβ, perror, D)	Parameters of the simplest radio model. The defaults are given on the right.	(2,0.45,0.02,0.05,0.1)
MAC waiting/backup times (wt, bt)	These parameters are used in motes for waiting for a channel and backup if the channel is busy. The defaults are given on the right (unit here is bit time).	(200+128r, 100+30r) where r is random and has uniform distribution   in (0,1)
Packet length (L)	All packets have a fixed length L	960 bits

 

The topology model primarily specifies the topology of the network, i.e., the relative placement of nodes. The basic topology is a rectangular x-y grid. The grid size, spacing, shift, density, and offset parameters allows one to specify a variety of topologies, including triangular grids, long parallel lines, and random networks of various kinds.

 

Name	Explanation	Typical Values
Grid Size (nx, ny)	Numbers of grid points in x and y directions.	(10,10), (20,20), …, (100,100)
Grid Distance (lx, ly)	Distance (spacing) of the grid points in x and y directions. The covered area is nxlx by nyly.	(1,1), (1,5)
Grid Shift (sx, sy, w)	Shift of the grid points from one row/column to the next as a percentage of grid spacing. Given a grid point (i, j), its position is shifted by               ((j-1)sxlx, (i-1)syly). To be even more general, one may specify sx, sy, where sx is a vector of shifts with size nxdx and/or sy is a vector of shifts with size nydy. Given one grid point at (i, j), its position is shifted by           ((j-1)sx(i)lx, (i-1)sy(j)ly). In case, one may specify sx (or sy) as a vector with the size < sxdx (or < sydy) then the algorithm will after going thru sx(i) (or sy(i)) continue with sx(1) (or sy(1)). Furthermore, one may choose either wrap around (w=1) or not (w=0).	(0,0,0), (0.5,0,1), …     ([0.1:0.1:0.7],0,0)…
Grid Density (dx, dy)	Number of nodes per side from grid point to grid point (extending out from the last grid point in each row and column). The total number of nodes is nxny(d­x+dy­–1).	(1,1), (1,4), …
Grid Offset (ox, oy)	Maximum random offset (distance, positive number) for nodes to be placed away from specified node position. Given node position (px, py) as determined by spacing, shift, and density, the actual position is (px+rxox, py+ryoy), where rx and ry are random variables in the interval [-1,1] with uniform distribution. Large offset values simulate a network with randomly positioned nodes.	(0,0), (0.5,0.5), …
Holes (x, y, rx, ry, q)  and/or Rand Holes (n, rx, drx, ry, dry) Border (b)	A specific position and size for one hole could be specified (e.g., center of the network), where (x, y) is the center of the rectangular area, q is the orientation of the x axis of the rectangle, and rx and ry specify the size of the rectangle. Furthermore, a number of randomly-centered  holes can be specified. In this case, n is the number of holes, drx and dry are maximum deviation from the nominal values of rx and ry, with uniform random distribution. Variation: the impacted nodes are moved to the boundary (b=1) of the rectangle. This allows one to simulate the dense placement of nodes around high-interest areas such as buildings, or nodes that fell from roofs around a building. Variation: one could specify the percentage of failed nodes in the hole.	(nxlx/2, nyly/2, 5,5,34) or (5, 10, 0.3, 6, 0.2) generates 5 random holes with rx between 7 and 13, ry between 4.8 and 7.2 and a randomly θ
Alive Rate (a)	Percentage of alive nodes. Allows one to specify a failure rate distributed over the network, e.g., due to placement impact (initial configuration).	(0.9) (= 10% Failure Rate)

 

 

Examples:

default values: (nx, ny) = (7,7), (lx, ly) = (1,1), (sx, sy, w) = (0,0,0), (dx, dy) = (1,1), (ox, oy) = (0,0), (x, y, rx, ry, q) = (0,0,0,0,0), (n, rx, drx, ry, dry) = (0,0,0,0,0), (b) = (0), (a) = (0):	(lx, ly) = (5,5):
(sx, sy, w) = (0.3,0,1):	(sx, sy, w) = ([0.1:0.1:0.4],0,0):
(dx, dy) = (3,3):	(ox, oy) = (0.1,0.1):
(ox, oy) = (3.5,3.5):	(nx, ny) = (10,10), (x, y, rx, ry, q) = (4,4,6.4,6.4,45), (b) = (1):
(nx, ny) = (25,25), (x, y, rx, ry, q) = (4,9,0.2,5,0.3), (b) = (1):

To be even more general, in addition to the parameterized topology model, one can input an arbitrary topology (from real experiments) from a file which specifies each node's location.

Application Model:

Rmase provides a parameterized application model that specifies the characteristics of routing applications. For simplicity in modeling and simulation, we assume that all the nodes in a sensor network, except source and/or destination nodes, are static. Although simplified, this assumption does fit most routing applications in sensor networks.

Using this model, one can specify the type of source/destination to be static, dynamic, or mobile. A source (or destination) is static if all the source nodes are static and remain the source nodes for the course of routing. A source (or destination) is dynamic if the source (or destination) nodes are static but changing during the course of routing. A source (or destination) is mobile if the source (or destination) nodes are fixed but moving during the course of routing. One can also specify the center of the source (or destination) c, the
radius r, and the percentage p of the nodes within the region to be source (or destination) nodes, i.e., if a node is within the circle centered at c with radius r, the probability of being a source (or destination) node is p. If only one node can be the source or destination within the specified circle (e.g., after leader selection),  the uniqueness flag can be checked in the model. In addition, if the source (or destination) is dynamic or mobile, one can specify the speed of motion. For a dynamic source (or destination), the speed represents the speed of a stimuli at the center; the source (or destination) nodes are selected at certain sampling time relative to the speed. For a mobile source (or destination), the source (or destination) nodes are selected in the beginning and are set to move according to the speed.

The application model can generate peer-to-peer (one-to-one), multicast (one-to-many), or convergecast (many-to-one) routing application scenarios. For example, one can set a static peer-to-peer communication scenario by specifying the source and the destination to be static and unique. To test a multicast scenario, one can have a unique source, but multiple destinations. Similarly, for a convergecast scenario, one can have a unique base station with multiple sources.

In addition to the geographic locations/distributions of sources and destinations, one should specify the source or destination rates, where the source rate is corresponding to the frequencies of events and the destination rate is corresponding to the frequencies of queries in query-based applications. The source/destination rate is specified by the number of packets per second. One may also have irregular event or query rates by providing an input file which specifies the exact time that each node sends out an event or a query packet. Such an input file is normally generated by real experiments in a hardware platform. Other parameters such as network start time for initialization, random source/destination pairs can be specified as well.
 

Name	Explanation	Typical Values (examples)
Source spec: (t, c, r, p, u, v)	Type, center (or random location), radius, percentage, uniqueness, and velocity (fixed in x and y direction plus random increment for both) of the source(s) from which routing requests originate. The type is either stationary, meaning fixed in the beginning, or dynamic, meaning different from time to time, or mobile, meaning the set of motes is fixed, but moving along the given speed. The center is typically either random or fixed. An area of source nodes is given by the radius r of a circle from which sources are taken. Percentage specifies the percentages of nodes in the area that are source nodes. The uniqueness parameter specifies if there is only one node in the specified area to be the source node. If source is dynamic or mobile, velocity is given.	(static, random, 0.2, 1, true, (0,0,0)), (static, (x,y), 10, 0.5, false, (0,0,0)), (static, random, 10, 1, false, (0,0, 0.1)), (dynamic, (x,y), 10, 0.1, true, (0.2,0.2,0)) (mobile, random, 0.5, 1, true, (0.2,0.2,0.1))
Desti. spec: (t, c, r, p, u, v)	Same as source spec.	See source spec.
Routing distance check (l, d, c)	Average distance l and maximum deviation d of that distance between source(s) and destination(s) (as a percentage of the maximum Euclidean distance between any two nodes in the network). If c is true, check if the pair distance is within range (for random source and destination). This allows one to specify a uniform separation for randomly generated sources and sink for repeated experiments.	(0.5, 0.1, true)
Source rate	Number of packets sent per second.	4 p/s
Desti. rate	Number of packets requested per second by the destination (used for query application).	0.5 p/s
Query window	Window for getting interested events in (used for query application)	1s
Number of source packets	Total number of packets sent from each source	infinite 10
Initialization time	Start time for sending data; used for initialization of the network.	1s

 

Performance Model:

Rmase provides a set of performance metrics for comparing different routing algorithms, including  latency, throughput, success/loss rate, energy consumption/efficiency, and network life-time predication.
 

Name	Definition	Comment
Latency	Time to send a message from source to destination. For any destination, if n packets have arrived, latency for that destination is given by Si di/n, where di is the latency of the ith packet. The latency of the network is then averaged by the number of destinations.	We use latency rather than the number of hops as the metric since latency consists of not just the number of hops, but also the length of transmission queues, the random delays at the MAC layer, and even deliberately added delays in routing algorithms to avoid collisions.
Jitter	Variance of time delays of packets over time. For any destination, if n packets have arrived, jitter is given by Si (di–m)2/(n–1), where di is the latency of the ith packet and m is the average latency at the destination. The jitter of the network is then averaged by the number of destinations.	Measures performance consistency.
Throughput	Number of messages per second received at destination. The throughput of the network is the sum of the throughputs from all destinations.	Measures time performance for entire application.
Success Rate	The total number of packets received at all the destinations vs. the total number of packets sent from all the sources.	Measures the overall success of the network.
Loss Rate	Number of lost packets vs. the total expected number of packets for that destination. To obtain the loss rate, each packet is attached with a message ID m and a sequence ID s. Assume that s' is the largest sequence ID of message m received at this node, when a new packet of m with s arrives, the loss for the packet is calculated by s - (s'+1) if s>s', and -1 otherwise. The total loss at a destination is then calculated by L=Si li, where li is the loss for the ith packet. The loss rate at a destination is L/(L+R), where L is the number of packets lost and R is the number of packets received. The loss rate of a network is then averaged by the number of destinations.	Measures quality (e.g., more dropped messages result in lower sensing resolution).
Energy Consumption (Pt, Pr, Pi)	Sum of used energy of all the nodes in the network, where the used energy of a node is the sum of the energy used for communication, including transmitting (Pt), receiving (Pr) and idling (Pi). Assume the transmission power level be L, and the time for transmitting, receiving and idling be Tt, Tr and Ti, respectively, the total energy consumption of a node is: PtTtL+PrTr+PiTi.	One can control a node to sleep or wakeup. There is no energy consumption in sleep state.
Energy Efficiency	Ratio between the total number of packets received at the destinations vs. the total energy consumption in the network.	There is a trade-off between throughput and energy consumption.
Life-time Prediction*	E – (u+σ), where E is the total initial energy at each node (full battery charge), u = S ui/N is the average used energy, N is the total number of nodes in the network, and σ2 = (ui–u)2/N.	Measures the effect of energy efficiency and load balancing on the routing application. Can be obtained at any time to predict the life-time of the network. From this metric, one can see that if two algorithms A and B use the same amount of energy, but if B uses energy more evenly across the network than A, B has a longer life-time.

^*Note that another definition for network lifetime has been the time until network separation. This definition has the disadvantage that it cannot distinguish between separation of half the network and separation of a single node, and between a single node that is peripheral and a single node that is the base station. Another definition can be the time until the network loss rate is above a given threshold. Loss rate measures the relevance to the application: a single connected peripheral node leads to a small loss rate, while a single disconnected base station leads to a large loss rate (if it is the source or the destination). Similarly, separation of half the network leads to a large loss rate. However, both of these definitions require to run the simulation until the property of life-time is satisfied. If the initial energy level is high, this may take a long time, which is not practical.