Citation
Dynamic architecture-reconfiguration algorithms and transmission protocols for clustered sensor network topologies with prioritized data

Material Information

Title:
Dynamic architecture-reconfiguration algorithms and transmission protocols for clustered sensor network topologies with prioritized data
Creator:
Salem, Fatma S
Publication Date:
Language:
English
Physical Description:
xii, 103 leaves : ; 28 cm

Subjects

Subjects / Keywords:
Sensor networks ( lcsh )
Signal processing -- Digital techniques -- Mathematics ( lcsh )
Algorithms ( lcsh )
Computer network protocols ( lcsh )
Algorithms ( fast )
Computer network protocols ( fast )
Sensor networks ( fast )
Signal processing -- Digital techniques -- Mathematics ( fast )
Genre:
bibliography ( marcgt )
theses ( marcgt )
non-fiction ( marcgt )

Notes

Bibliography:
Includes bibliographical references (leaves 100-103).
General Note:
Department of Electrical Engineering
Statement of Responsibility:
by Fatma S. Salem.

Record Information

Source Institution:
|University of Colorado Denver
Holding Location:
|Auraria Library
Rights Management:
All applicable rights reserved by the source institution and holding location.
Resource Identifier:
747100928 ( OCLC )
ocn747100928
Classification:
LD1193.E54 2011m S34 ( lcc )

Full Text

DYNAMIC ARCHITECTURE- RECONFIGURATION ALGORITHMS
AND TRANSMISSION PROTOCOLS FOR CLUSTERED
SENSOR NETWORK TOPOLOGIES
WITH PRIORITIZED DATA
by
Fatma S. Salem
B.S.E.E. Omar Al- Mukhtar University, 2001
A thesis submitted to the
University of Colorado Denver
in partial fulfillment
of the requirements for the degree of
Master of Science
Electrical Engineering
2011


The thesis for the Master of Science
degree by
Fatma S. Salem
has been approved
by
Jan Bialasiewicz
Hamid Fardi
.C'ri


Salem, Fatma S. (M.S., Electrical Engineering)
Dynamic Architecture- Reconfiguration Algorithms and Transmission Protocols for
Clustered Sensor Network Topologies with Prioritized Data.
Thesis directed by Professor Titsa Papantoni
ABSTRACT
The objective of a sensor network is the execution of specific signal
processing functions on data that are collected in a distributed fashion. The signal
processing operations are constrained by power limitations of the units and
communication costs, but require a minimal level of performance; the performance
criteria are dictated by the specific signal processing operation and include
convergence rates. Furthermore, the final signal processing operations are performed
by a subset of network nodes, called Fusion Centers, whose outputs are the answers to
the network objectives.
The transmission of preprocessed (by other nodes) data to the Fusion Centers
is facilitated by data transmission protocols whose operations may be constrained by
physical limitations of the network units, while their performance must
simultaneously comply with the performance requirements of the deployed signal
processing operations. At the same time, the network architecture affects the
performance of both the signal processing and the data transmission operations, while
some of the sensors may generate high priority data.


This thesis considers sensor network with a specific signal processing
objective. The network organized in architecture comprised of sensor clusters whose
cluster heads are connected via a backbone network, where a specific random access
transmission algorithm per cluster is deployed, which facilitates high priority data.
Then it introduces a dynamic architectural reconfiguration algorithm which controls
individual cluster rates for optimal overall network performance. The latter algorithm
is facilitated by a high level traffic rate monitoring protocol, which detects changes in
cluster traffic rates and dictates subsequent adaptation in the deployed traffic
allocation techniques.
The transmission protocol, the high level traffic rate monitoring protocol and
the dynamic architectural reconfiguration algorithm are evaluated via MATLAB
programs that simulate the performance characteristics of the overall system.
This abstract accurately represents the content of the candidates thesis. I
recommend its publication.
Signed


DEDICATION
I dedicate this thesis to my parents, who gave me an appreciation of learning and
taught me the value of perseverance and resolve. 1 also dedicate this thesis to my
husband for his unfaltering support and understanding while I was completing this
thesis.


ACKNOWLEDGEMENT
My thanks to my advisor, Dr. Titsa Papantoni, for her contribution and support to my
research. I also wish to thank all the members of my committee for their valuable
participation and insights.


CONTENTS
Figures.....................................................................ix
Tables.....................................................................xii
Chapter
1. Introduction to Wireless Sensor Networks................................1
1.1 Hardware and Applications................................................1
1.2 Key Definitions of Sensor Networks......................................2
1.3 Distinguishing Feature and Constraints...................................3
2. System Model and Problem Formalization...................................5
2.1 The Static Problem.....................................................9
2.2 The Dynamic Problem....................................................9
3. The Per Cluster Random Access Transmission Protocol...................11
3.1 The Algorithm for the Two Channel System..............................17
3.2 Expiration of the MSNs during the Transmission Process..................21
3.3 Algorithmic Analysis of the Two Channel System..........................26
3.4 Numerical Results and Their Evaluation for the Two-Channel System
with Expiration Model.................................................33
4. The Data Rate Monitoring Protocol.......................................53
4.1 The Algorithmic System................................................54
4.2 The Algorithm for the Poisson.........................................58
vii


4.3 Numerical Results and Their Evaluation for the Two-Channel Monitoring
Algorithmic System....................................................59
5. An Architectural Reconfiguration Algorithm..............................70
5.1 The Algorithm...........................................................71
5.2 Numerical Results and Their Evaluation for the Architectural Reconfiguration
Algorithm.............................................................73
5.3 A Specific Experimental Scenario........................................78
6. Overall System Issues...................................................84
7. Conclusion..............................................................86
Appendix
A. Algorithmic Analysis of the Two-Channel System..........................88
B. The Performance of the Data Rate High Level Monitoring Protocol.........95
B.l Performance Characteristics of a Simple Algorithmic System..............95
B.2 Re-Initialization Performance...........................................97
References.................................................................100
viii


OJ Lk) LJ
FIGURES
Figure
1.1 Berkeley/Crossbow Sensor Mote, Alongside a U.S Penny and an Early
Prototype of Smart Dust MEMs Integrated Sensor...................1
2.1 Physical Topology and Backbone network................................7
3.1 Expected Delays for the 3-Cell Algorithm.............................14
.2 Expected Delays for the 2 and 3-Cell Algorithms......................15
.3 Expected Delay for the 3-Cell Algorithm 2; = 100, q = 20. P = 10.....22
.4 Rejection Rate for the 3-CeII Algorithm 2; = 100. r| = 20, P = 10....23
.5 Expected Delay for the 3-Cell Algorithm 2; = 100, q = 50, P = 10.....24
.6 Rejection Rate for the 3-Cell Algorithm ^ = 100, q = 50, P = 10......25
.7 Maximum Maintainable Poisson Rates Window Size: A = 2.5599...........29
.8 Expected Delays. Symmetric Two-Channel System with Regular
MSN Rates Equal To 0.1.............................................31
.9 Expected Delays. Symmetric Two-Channel System with Regular
MSN Rates Equal To 0.3.............................................32
3.10 Expected Delays. Symmetric Two-Channel System
$= 100. q = 20, p = 5.............................................35
3.11 Rejection Rates. Symmetric Two-Channel System
S= 100, q =20, P = 5..............................................36
3.12 Expected Delays. Symmetric Two-Channel System
2; = 200. q = 20, P = 5...........................................37
3.13 Rejection Rates. Symmetric Two-Channel System
2; = 200, q = 20, P = 5...........................................38
IX


^ OJ UJ L*J
3.14 Expected Delays. Symmetric Two-Channel System
2; = 300, p = 20, P = 5.........................................39
3.15 Rejection Rates. Symmetric Two-Channel System
2j = 300, p = 20, P = 5.........................................40
3.16 Expected Delays. Symmetric Two-Channel System
5= 100, p = 30, p = 5...........................................41
.17 Rejection Rates. Symmetric Two-Channel System
S= 100, r| =30, (3 = 5..........................................42
.18 Expected Delays. Symmetric Two-Channel System
2; = 200, p = 30, P = 5.........................................43
.19 Rejection Rates. Symmetric Two-Channel System
2; = 200. p = 30, P = 5.........................................44
.20 Expected Delays. Symmetric Two-Channel System
2; = 300, p = 30, P = 5.........................................45
.21 Rejection Rates. Symmetric Two-Channel System
2; = 300, p = 30, p = 5.........................................46
.22 Expected Delays. Symmetric Two-Channel System
5= 100,p = 60, (3 = 5...........................................47
.23 Rejection Rates. Symmetric Two-Channel System
1= 100, ri = 60, P = 5..........................................48
.24 Expected Delays. Symmetric Two-Channel System
S = 200. p = 60, p = 5..........................................49
.25 Rejection Rates. Symmetric Two-Channel System
2; = 200, p = 60, p = 5.........................................50
.26 Expected Delays. Symmetric Two-Channel System
^ = 300, p =60, p = 5...........................................51
.27 Rejection Rates. Symmetric Two-Channel System
^ = 300, p =60, p = 5...........................................52
4.1 Time Evolution of the Two-Channel Monitoring Algorithmic System...56
4.2 False Alarm and Power Curves for the u to / Monitoring Algorithm..57
x


4.3 Rejection Rates. Two Channel Monitoring Algorithmic System
$ = 100, ri = 50, p= 10..................................................60
4.4 Packet Delay Distributions. Two-Channel Monitoring Algorithmic
^ = 100, r[ = 50, p = 10.................................................61
4.5 Expected Delays. Two-Channel Monitoring Algorithmic System
$ = 100, n = 50, p = 10..................................................62
4.6 Rejection Rates. Two-Channel Monitoring Algorithmic System
\= 100, T1 = 10, P = 5...................................................64
4.7 Packet Delay Distributions. Two-Channel Monitoring Algorithmic System
5= 100, T| = 10, P = 5...................................................65
4.8 Expected Delays. Two-Channel Monitoring Algorithmic System
s= 100, T1 = 10, p = 5...................................................66
4.9 Rejection Rates. Two-Channel Monitoring Algorithmic System
^ = 200. p = 30, p = 10..................................................67
4.10 Packet Delay Distributions. Two-Channel Monitoring Algorithmic System
2; = 200, r| = 30, P = 10................................................68
4.11 Expected Delays. Two-Channel Monitoring Algorithmic System
2; = 200, r| = 30, p = 10................................................69
5.1 SubsystemsRejection Rates..................................................74
5.2 Subsystems Delay Distribution..............................................76
5.3 Subsystems Expected Delays.................................................77
5.4 Rejection Rats for locals =100, ^highpriority =130. r\ =50 and p =10........78
5.5 Delay Distributions for locals =100, ^hjghpriority=130, r| =50, and P =10...79
5.6 Expected Delay for ^ocals =100, ^highpriority=130, r\ =50, and P =10........80
5.7 Rejection Rats for ^0Cais 100, ^highpriority =200, r| =50, and P =10.......81
5.8 Delay Distributions for locals =100, ^highpriority =200, p =50. and =10.....82
5.9 Expected Delay for locals =100, ^highpriority =200, r| =50, and P =10.......83
xi


LJ
TABLES
Table
2.1 Notation................................................................8
3.1 Expiration model........................................................21
.2 Maximum maintainable Poisson rate window size: A = 2.5599..................28
xii


1. Introduction to Wireless Sensor Networks
1.1 Hardware and Applications
Wireless sensor networks involve setting up a large number of small
inexpensive nodes, such as the ones pictured in figure 1.1, [31] which could either
have a fixed location or be mobile and which might be randomly deployed to monitor
their environment. The power of wireless sensor networks lies in their ability to
deploy a large numbers of such inexpensive nodes and network them via low power
wireless communications. The deployed nodes collect then data from the environment
and transmit them to other nodes over flexible network architecture. Each node is
properly equipped to perform some processing on gathered information and to
communicate with other connected nodes in the network. Each node consists of one
or more sensors, a microcontroller, external memory, transceiver, and a power source.
These components are incorporated on a single or multiple boards, and are packaged
within a few cubic inches.
Figure 1.1: Berkeley/Crossbow Sensor Mote, Alongside a U.S Penny and an Early
Prototype of Smart Dust MEMs Integrated Sensor.


The wireless arena has been experiencing a rapid growth in the past decade,
where wireless sensor networks represent a trend that emerged in the past few years;
their development was motivated by military applications such as battlefield
surveillance. Wireless sensor networks (WSNs) are now used in a variety of industrial
and civilian applications, including industrial quality monitoring and control,
environment monitoring, healthcare applications, and traffic control. Descriptions of
general applications for WSNs can also be found in [31], [32].
1.2 Key Definitions of Sensor Networks
The design of wireless sensor networks depends on the consideration of many
diverse factors and their study is challenging: it requires an enormous breadth of
knowledge from an enormous variety of disciplines. The design and operation of
WSNs involves multidisciplinary research activities and draw from the contributions
of signal processing techniques, networking and transmission protocols, distributed
algorithms, embedded systems and network architecture. In the following, we define
a number of key terms that will be used throughout the thesis, as we develop
protocols and algorithms for WSNs.
MSN: (Micro Sensor Node) is the basic unit in a sensor network. When a node has
only a single sensor on a board, the node is sometimes also referred to as a sensor.
AFN: (Aggregating and Forwarding Node) is a network node that collects local data
and processes them (cluster head).
BS: (Base Station) fuses the data transmitted to it by the neighboring AFNs.
Clustering: The nodes in a sensor network often need to organize themselves into
clusters. Clustering allows hierarchical structures to be built on the nodes and enables
more efficient use of limited resources, such as power, frequency spectrum, and
bandwidth.
2


Routing: It is the process of determining a network path from a data generating source
node to the node of the data destination.
Rate: The average number of data arrivals per time unit.
Throughput: The maximum total traffic rate maintained by the transmission protocol
with finite delays.
Performance metric: A measurable quantity that describes how well the system is
performing on some absolute scale, such as packet rejection rate and delay time.
1.3 Distinguishing Feature and Constrains
Wireless sensor networks satisfy signal processing objectives; their
performance metrics are thus determined by those of the latter objectives [19]. When
time constraints are imposed on high accuracy signal processing operations, the
consequence is increased required overall data rates. At the same time, in wireless
sensor networks, observation data are transmitted via appropriate multiple access
protocols, [12], [22], [24], [26] whose performance is a function of the their input
data rates; and are collected and processed by life-limited nodes, whose life-span is a
function of the data rates they process, [1], [14], [15], [17].
Thus, required overall data rates, in conjunction with rate-dependent
transmission protocol performance and node life-spans, necessitate network-
architecture and network-operations adaptations, so that the nodes' life span
limitations do not interfere with the required overall network performance, [4], [30].
Since the network-architecture and network-operations adaptations are functions of
the acting data rates, it is eminent that data rates be monitored and rate changes are
detected accurately and rapidly [23],
The unique feature in wireless sensor networks is the limited life-spans of the
nodes due to the energy consumption. Interesting results focusing on energy
consumption have been obtained by several researchers: Bounds on energy
j


conservation techniques have been derived in [5], role assignments targeting energy
conservation have been developed in [4], energy conservation routing techniques
have been proposed in [14], [15], [16] and issues arising due to energy conservation
have been addressed in [16].
In addition, topological and node-cooperation issues have been included in
[29], [30], while approaches to performance monitoring have been presented in [11],
An interesting rate allocation algorithm has been presented in [17], which is based on
a modification of the max-min routing in [3] and the lexicographic linear
programming approach in [20]. In [23], a dynamic rate allocation methodology has
been presented that is facilitated by a powerful data rate monitoring algorithm. In [2],
energy efficient clustering algorithms are proposed, where energy consumption is
assumed to be strictly a function of geographical distances and where transmission
collisions are completely ignored.
This thesis considers clustered sensor network topologies containing sensors
that generate high priority data, where a specific random access transmission protocol
is deployed per cluster that facilitate high priority data. Data rates are time-varying in
such a network, mainly due to expiring life-limited nodes. We focus on the problem
of dynamic architectural reconfigurations, facilitated by a data rate monitoring higher
level protocol.
4


2.
System Model and Problem Formalization
Figure 2.1 shows a clustered network architecture, as this considered in [17]
and [23]. The components in the architecture are micro-sensors, micro-sensor clusters
and a backbone network of cluster-heads and a fusion-center. For the purpose of
consistency, this thesis will use the same terminology in [17] and [23] where the
micro-sensors, the cluster-heads and the fusion-center have been respectively termed
Micro-Sensor Nodes (MSNs), Aggregation and Forwarding Nodes (AFNs) and Base
Station (BS). Given a pre-determined signal processing objective, the MSNs, AFNs
and BS perform the following functions: (a) The MSNs are grouped into distinct
clusters, where each cluster contains a single AFN. Each MSN collects local data and
transmits them to its local AFN, via some multiple access transmission protocol
implemented on a distinct channel associated with the AFN; that is, the overall
network encompasses distinct separate channels (such as distinct frequency bands),
each associated with a single AFN.
Since the identity of the sensors contained in each cluster may change due to
sensor possible expiring and subsequent architectural reconfigurations, the
appropriate class of the deployed multiple access protocols is the Random Access
Class, (RAs) [11], [12], [22], [24] [26], This concept will be discussed in much detail
in chapter 3. The MSNs are low-cost and low-energy; thus, short-life devices, and
some of them generate high priority data that must be received by the corresponding
AFNs in relatively short time, (b) Each AFN collects the data sent by its local MSNs
and processes them, using an operation determined by the network signal processing
objective [19]; it also receives processed data sent by other neighboring AFNs. The
AFN then processes the compounded processed data, utilizing an operation that is
determined by the network signal processing objective [19], and transmits the
outcome to selected neighboring AFNs or the BS.
5


The AFNs have processing capabilities and are devices with energy and life-
spans that are much higher than those of the MSNs; however their life-spans and
energy are still limited, (c) The BS fuses data transmitted to it by neighboring AFNs.
utilizing an operation that is determined by the network signal processing objective
[19]. The BS has unlimited life-span and processing power.
6


o o
Physical Topology
Backbone Network
Figure 2.1 Physical Topology and Backbone network
7


The MSNs transmit to their assigned AFN via a RA protocol. Operations are
performed at the AFNs and the BS which constitute the backbone network. The
nature of the operations is determined by the network signal processing objective, the
environment that generates the data and the data rates all [19], At the same time, the
energy consumption of the AFNs is a function of the data rates they receive and
produce, and the complexity of the operations they perform. Each AFN performs
operations on its input data rates, to produce the data rates it outputs to neighboring
AFNs and/or the Base Station (BS). Let us define some notations in table 2.1
Table 2.1 Notation
^Ci The data rate from the MSNs in the cluster of the ith AFN to the AFN, where kci = 0 if all the MSNs in the cluster have expired.
T The time constraint imposed on the network for completing the designated signal processing operation.
The data rate collected by the BS.
We will assume that the MSNs per cluster are spatially randomly and
independently distributed, and their number is large. In addition, their life-span is
short: Thus, each MSN basically transmits a short duration data message/or signal
and expires. This, gives rise to a limit Poisson data packet user model per cluster [22];
that is, the cluster user model reflects infinitely many independent Bernoulli users,
each generating a single data packet, where an overall Poisson data packet traffic is
induced
8


2.1 The Static Problem
We initially consider the static problem stated in [23] and [17]: The network
signal processing objective is specified, the network architecture is fixed, the data
environments and the RA transmission protocols are known and unchanged, the
operations performed by the AFNs are determined and the data rates {Aci} generated
in the clusters are fixed.
Given, in addition, the time constraint T, for the completion of the signal
processing objective, is specified, the performance of the network will be maximized
when the maximum number of data is fused in the time length T [17]. Since the
fusion operation is performed by the BS and since the maximum number of data in T
corresponds to the maximum attainable data rate, maximum network performance is
then attained when the data rate p in table 2.1 is maximized. A generally nonlinear
dynamic programming problem is then formalized to determine the optimal routing
protocol in the backbone network comprised of the AFNs and the BS. This is known
as the Static Rate Allocation problem, [23], [21]
2.2 The Dynamic Problem
The network is required to complete its signal processing objective within T
time units. During this time period, some MSNs generally expire, since their life-
spans are only fractions of the time period T. This expiration causes changes in the
cluster data rates {Aci} and thus induces dynamics, in the rate allocation problem
and then in the network architectural configurations. In particular, when the network
operates towards the satisfaction of its objective, the rates {ACj} may generally change
during the T time period. For rate changes that are relatively modest, a dynamic rate
allocation problem arises: if such changes of the rates {ACj} can be detected, then the
constants of the static rate allocation problem will be adjusted accordingly, and the
new data rate allocations will be then dictated by the solution of the adjusted problem.
9


For more dramatic detected rate changes, the satisfaction of the overall system
performance requirements may necessitate network architectural reconfigurations.
In order to detect changes in cluster data rates, an algorithm must be devised,
that detects those changes accurately and rapidly. Such algorithm will be deployed at
the AFNs, as an upper level protocol, it will detect changes and communicate them
across the AFNs. Then, either a static rate allocation algorithm on the unchanged
network architecture will be initiated that uses the newly detected cluster rates as
constants, or an architectural network reconfiguration will be implemented with a
matching rate allocation technique.
The data rates required for the communication among the AFNs will be a
fixed algorithmic characteristic, they will be added as permanently fixed constants in
the functions that interrelate network data rates [23] and will not interfere with the
dynamics of the resulting rate allocation and architectural reconfiguration problems.
The important performance characteristics of the rate monitoring algorithm
are accuracy, speed and stability, that is, the convergence rate (detection time)
induced by the algorithm compounded by the time to solve the static rate allocation
and architectural reconfiguration problems must be shorter than the time taken for
actual changes across the network (rate changes), while false detections must
simultaneously occur infrequently.
10


3.
The Per Cluster Random Access Transmission Protocol
Due to the dynamically changing architectural reconfigurations in the
considered sensor topologies, the identities of all sensors are not known to the AFNs
at all times. Thus, the unknown user population model arises, where the sensors are
the users in this case: the identity of each sensor becomes known to the system, only
after the sensor accesses successfully some AFN. The only possible class of
transmission protocols for the unknown user population model is the Random Access
(RA) class, [25], In addition, within the RA class of transmission protocols, the only
implementable sub-class is the class of Limited Sensing Random Access Algorithms
(LSRAAs), where it is required that upon generation of a message, each user starts
monitoring the channel feedbacks continuously, until this message is successfully
accepted for transmission, [12], [22], [24], [26].
As stated in chapter 2, we assume a limit Poisson data packet user model per
cluster. We will also assume a synchronous system, where all AFN channels are
slotted synchronously across all AFNs, and where a slot is the time corresponding to
the transmission of a single packet. In this model, each packet represents a separate
independent user (separate MSN here); thus, any number of packets may
simultaneously attempt transmission, unless organized by some protocol; an LSRAA,
in this case.
As stated in chapter 2, the MSNs in a single cluster transmit through a single
channel (to their AFN) and overall system connectivity is attained via the backbone
network. Due to the possible MSN mobility or the dynamics of the architectural
topology, some MSNs may move across clusters, while they have a packet to
transmit. At cluster boundaries, such MSNs are exposed to feedbacks from more than
one cluster channels and have the capability to transmit through anyone of those
11


channels. The latter phenomenon can be exploited to avoid temporary isolation of
users moving across clusters, and especially to reduce their transmission delays while
in transit across clusters. In addition, some MSNs may generate high priority data,
requiring accelerated transmission.
We encompass boundary MSNs into the high priority category and name them all
high priority MSNs. We name non-high priority MSNs, regular MSNs. The following
approach can be then taken: To each regular MSN assign as a single channel for its
transmissions that corresponding to its local AFN. To each MSN that is high priority,
provide the capability to monitor and possibly transmit through a group of channels,
instead, associated with the corresponding group of AFNs. The MSNs can be then
partitioned into two categories: the regular MSNs transmitting through a single local
channel and the high priority MSNs having access to several cluster- channels.
If we consider the environment where high priority MSNs have access to M AFN
channels, then incorporating the regular MSNs, M+l classes of MSNs arise: (a) M
classes of regular MSNs, each class transmitting through one of the distinct M AFN
channels, and (b) the (M+l)th class of high priority MSNs that have access to all the M
AFN channels.
The objective is the design of Limited Sensing Random Access Algorithms
(LSRAAs) for the system that require no knowledge of the system state by the users and
present the high priority MSNs with a delay advantage (compared to the non high priority
MSNs), even when the traffic rates in the system change dynamically, while keeping the
delays of the regular MSNs as low as possible. When architectural reconfigurations, as in
chapter 5, are in place, each regular MSN selects one of the AFNs equiprobably, while
each high priority MSN selects one M-size group of AFNs, equiprobably among all
possible such groups, for their transmissions.
For the multi-channel system considered in the above paragraph, let the M
channels be indexed from 1 to M. Then, the regular MSNs assigned to channel i
deploy a limited sensing random access algorithm, named LSRAAi. for their
12


transmissions. For each of these LSRAAs, we adopt the class of limited sensing
random access algorithms in [ 12] due to their simple operational properties and their
performance characteristics: the algorithms are easily implemented in the limited
sensing environment, they operate with binary (collision versus non-collision)
feedback, they have superior resistance to feedback errors and in the presence of the
limit Poisson user model they attain a throughput of 0.43. Throughput is here defined
as the highest traffic rate maintained by the algorithm with finite delays. The delay
experienced by the nth packet in the system is defined as the time difference between
its arrival and the end of its successful transmission. Figure 3.1 shows the average
delay in slot units against different values for the arrival rate for the class of LSRAAs
that considered in this thesis (K=3).


14


As K increases, we expect that the delays for low rates will increase, as exhibited
in Figure 3.2. We note that, as compared to the 2-cell algorithm, the 3-cell algorithm
induces somewhat increased delays at low rates, at the gain of lower delays at high rates.
0
0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4
Arrival Rate
Figure 3.2 Expected Delays for the 2 and 3-Cell Algorithms
15


The high priority MSNs in the system deploy the same LSRAA as that the local
MSNs do, in conjunction with a selection policy via which they choose their transmission
channel. A selection policy may be either dynamic or probabilistic. The operations of a
dynamic selection policy are dictated by the feedback sequences that the boundary MSNs
observe. In contrast, a probabilistic selection policy is represented by a priori assigned
probabilities. A probabilistic selection policy is simple, but it does not generally present
the high priority MSNs with significant delay advantage, especially in the presence of
changing rates of the regular MSN traffics.
This thesis proposes a dynamic selection policy which does not require any a
priori system state knowledge, and which indeed presents the high priority MSNs with a
significant delay advantage. The policy, which was first introduced in [24], induces light
delay penalization for the regular MSNs, at the expense of a reduction in overall system
throughput.
Considering an M-channel system as above, we assume that some
synchronous LSRAA is deployed by all the MSNs in the system. In particular: (1)
Time is divided into slots of length equal to the duration of a packet, and the starting
instants of the slots are identical in all channels. (2) Per channel, feedback per slot
exists and corresponds to the outcomes induced by the local LSRAA. This feedback
is binary, collision versus non-collision (NC). (3) Each local MSN is required to
monitor the feedback from its assigned channel continuously from the time it
generates a new packet to the time that this packet is successfully transmitted. We
initially assume that no propagation delays and no forward or feedback channel errors
exist in the system.
We also assume that each high priority MSN receives the feedbacks from all
channels correctly and without propagation delays. At the time when a high priority MSN
generates a new packet, it starts monitoring the feedbacks from all channels continuously
until it decides to join the operations of one of the LSRAAs for the transmission of its
packet. Upon this decision, it maintains the continuous monitoring of only those
16


feedbacks that correspond to the LSRAA it chose, until its packet is successfully
transmitted.
The regular MSN populations for each channel and the high priority MSN
population are all modeled as limit Poisson. That is, it is assumed that the regular data
packet traffic i, i = 1, 2,..., M is a limit Poisson process with intensity Aj, i = 1,2,..., M
and that the data packet traffic generated by the high priority MSNs is another
independent limit Poisson process with intensityAM+1. As an interesting remark, for a
large class of LSRAAs, including that considered in this thesis, the limit Poisson user
model provides a lower bound in performance within the class of identical and
independent users whose packet generating process is independent and identically
distributed (i.i.d.).
3.1 The Algorithm for the Two-Channel System
We assume that the two LSRAAs in the two-channel system are identical and
belong in the class of window algorithms in [12], all of which induce throughput 0.43 and
operate with binary feedback, but different delay and resistance to feedback errors
behaviors.
Upon generation of a new packet, a high priority MSN imagines itself belonging
to the systems of both LSRAAs and follows their algorithmic steps until the first time
that they enter a collision resolution event in one of them: the rules of this first entry are
stated by the channel selection policy. Then, the MSN remains with the latter LSRAA
system, until its packet is successfully transmitted.
Let time be measured in slot units, where slot t occupies the time interval [t, t+1).
Let xt(j) denote the feedback that corresponds to slot t for channel j,j=l, 2, where
xt(j) = C and xt(j) = NC represent collision and non-collision slot t for channel j,
respectively. The LSRAA for channel j is implemented independently by each MSN in
the system; its steps are dictated by the feedback sequence {xt(j)}t. Each regular MSN
17


is assigned one of the channels a priori and thus observes only the feedback sequence
corresponding to the latter channel. Each high priority MSN observes, instead, the
feedback sequences of both channels until it selects the channel which it will transmit its
packet through. Below, we first explain the algorithmic steps implemented by each local
MSN, dropping the channel index j, for simplicity in notion.
Each algorithm in the class in [ 12] utilizes a window of size A as an operational
parameter and induces a sequence of consecutive Collision Resolution Intervals (CRIs). The
window length A is subject to optimal selection for throughput maximization. Each CRI
corresponds to the successful transmission of all packet arrivals within an arrival interval of
length A. The length of the CRI is determined by the number of MSNs in the window A and the
algorithmic steps of the collision resolution process. The placement of the A-size window on the
arrival access is determined asynchronously by the MSNs.
We will first describe the collision resolution process induced by the
algorithm. Then, we will explain the process which determines the placement of the
A-size window per CRI.
The algorithmic class contains algorithms whose collision resolution process can
be depicted by a stack with finite number of cells. Let us consider this algorithm in the
class which can be described by a K-cell stack. Then, in the implementation of the
collision resolution process, each MSN utilizes a counter whose values lie in the set of
integers, [1,2, , K], We denote by rt the counter value of some MSN at time t. The K
different possible values of the counter place the user in one of the K cells of a K-cell
stack. When its counter value is 1. the MSN transmits; it withholds at K-l different
stages otherwise. When a CRI begins, all MSNs in the A-size window set their counters
at 1; thus, they all transmit within the first slot of the CRI. If the window contains at
most one packet, the first slot of the CRI is a non-collision slot and the CRI lasts one slot.
If the window contains at least two packets, instead, the CRI starts with a collision which
is resolved within the duration of the CRI via the following rules:
18


The MSN transmits in slot t if and only if rt = 1. A packet is successfully
transmitted in t if and only if rt = 1 and xt = NC.
The counter values transition in time as follows:
If xt_1 = NC and rt_! = j; j = 2, 3, , k then rt = j 1
If xt_! = C and rt_1 = j; j = 2, 3, , k then rt = j
If xt_x = C and 1, then, rt -
1
D ' W'P K
1
D ;W'P K
1
D ;W'P K
1
K W P K
For any given K, the throughput of the algorithm is 0.43. This throughput is attained for
different optimal window sizes A*, as K varies. For K=2, A* = 2.33. For K=3, A* = 2.56.
From the above rules, it can be seen that a CRI that starts with a collision slot
ends with K consecutive non-collision slots, an event which cannot occur at any other
instant during the CRI. Thus, the observation of K consecutive non-collision slots signals
the certain end of a CRI to all users in the system; it either signifies the end of a CRI that
started with a collision or the end of a sequence of K consecutive length-one CRIs.
Therefore, a MSN packet that arrives in the system without any knowledge of the channel
feedback history can synchronize with the system upon the observation of the first K-
tuple of consecutive non-collision slots. This observation leads to the asynchronous by
the MSNs generating of the size-A window placement on the arrival axis. Specifically, if
a CRI ends with slot t, the window of the next CRI is selected with its right most edge
k 1 slots to the left of slot t and it contains those packets whose updates fall in the
interval(t K+l A, t K + 1).
19


The updates (tk) of a packet are generated as follows: Let t0 be the slot within
which a packet is generated. Then define t to be equal to t0. Starting with slot t ,the
corresponding local MSN senses continuously the channel feedbacks. It does so
passively, until it observes the first K-tuple of consecutive NC slots, ending with slot t|.
If t 6 (tx- K + 1 A, tx- K + 1) ,the MSN participates in the CRI that starts with slot
t-L + 1. Otherwise, it updates its arrival instant to t1 = t + A and waits passively until
the end of the latter CRI, ending with slot t2 If t1 G (t2- K + 1 A, t2- K + 1) the
MSN packet participates in the CRI which starts with slot t2; otherwise, the MSN updates
its arrival instant by A again and repeats the above process. In general, if {tn}, n > 1
denotes the sequence of consecutive CRI endings since the first K-tuple of consecutive
NC slots, the MSN packet participates in the kth CRI if tk_1 G (tk K + 1 A, tk
K + 1) and tn £ (tn+1 K + 1 A, tn K + 1) ; for all n < k 2 .
Each high priority MSN observes both feedback sequences {x(l)}t2ti and
{x(2)}t>ti and follows the evolution of both time sequences, {tj(l)}j>2 and {tj(2)}j>2 .
Iftk(l) < tk(2), then in slot tk(l) + 1 its packet enters a CRI within the LSRAA of
channel 1, and the packet is successfully transmitted during the process of this CRI. If
tk(l) > tk(2) instead, then he MSN packet joins a CRI in channel 2, in slot tk(2) + 1.
If tk(l) = tk(2) then the MSN selects one of the local LSRAAs with probability 0.5.
The evolution of the updates for each LSRAA and each boundary MSN is exactly as
those of the local MSNs. That is. the arrival sequences are always updated by A, and the
A-size window is equally divided between the two LSRAAs whenever tk(l) = tk(2)
20


3.2 Expiration of MSNs during the Transmission Process
The MSNs that have a packet to transmit consume energy due to channel
monitoring and due to retransmissions within the CRI of that accommodates the
transmission of the packet. If the energy consumed this way exceeds their limit, the
MSNs expire and their packet is lost. We will assume that the energy consumed per
single observed channel slot is a constant, and so is the energy consumed per
retransmission. Then, we form a linear expiration expression, as explained below. Let us
first define some notations in table 3.1.
Table 3.1 Expiration Model
p The amount of energy consumed by the monitoring of a single channel slot by a MSN
n The amount of energy consumed by a single packet (re) transmission by a MSN
Tl The number of slots during which a MSN monitors both channels in the System
X2 The number of slots during which a MSN monitors a single channel in the system
m The number of retransmissions during the CRI
The total energy stored in a single MSN for packet transmission
Using the above notation, we assume that the MSN expires, with subsequent loss of its
generated packet, if:
P(2ii + t2) + pm > (3.1)
As first stated in chapter 2, the MSN expiration, as given by expression (3.1),
causes packet rejections and subsequent reduction of cluster traffic rates. Other causes of
MSN expiration may be environmental hazards or random electronic failures. Regardless
21


of the causes, MSN expirations may result in traffic rate reductions that dictate
architectural reconfigurations. This concept is demonstrated in the following figures
which are the results of simulating the one channel system for the limit Poisson user
model along with the expiration model for different constants in (3.1). From the latter
figures we notice that the expected delays decreases with increasing rejection rate, since
more packets are then expired resulting in a decreased packet processing load.
4.1
Arrival Rate
Figure 3.3 Expected Delay for the 3-Cell Algorithm
5 = 100, r| =20, p = 10
22


0.4
0.05
0.1
0.15
0.2 0.25
Arrival Rate
0.3
0.35
0.4
Figure 3.4 Rejection Rate for the 3 -Cell Algorithm
^ = 100, ti=20, p = 10
23


3.7
3.68
Figure 3.5 Expected Delay for the 3-Cell Algorithm
5=100, r| = 50, p = 10
24


0.5
0
0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4
Arrival Rate
Figure 3.6 Rejection Rate for the 3 -Cell Algorithm
^=100, ri=50, (3= 10
25


3.3 Algorithmic Analysis of the Two-Channel System
We index the two channels from 1 to 2. Then, for convenience in notation, we
will refer to the regular MSNs in channel 1, the non high priority MSNs in channel 2 and
the high priority MSNs as subsystem 1, subsystem 2 and subsystem 3, respectively. In the
algorithmic analysis, we will assume that the three subsystem traffics are mutually
independent, and that the user traffic in subsystem j,j=l, 2, 3. is limit Poisson with
intensity Aj.
Consider either one of the local LSRAAs. whose operations are described in
section 3.1. Let us select the 3-Cell algorithm among those in the class in [12], In
Appendix A, the algorithmic analysis of the 2-channel system is presented. This
analysis includes stability, which provides the traffic rates maintainable by the
system. In Table 3.2, we include the maximum rate X*2 ; maintained by the system, for
varying X1 and Rvalues, as well as the maximum maintained symmetric rate
X*(X3) = A* = Ax = X3 for varying X3 values. We also include the maximum rate X3;
maintained by the system, when Ax = X2 = 0. We note that due to the symmetries
appearing in the system for each fixed rate X3 we only need to compute >4 for
values in the interval [0, A* (A3)]. In figure 3.7, we plot the boundaries of the (Ax, X2)
acceptable regions of maintainable traffic, parameterized by various A3 values. Those
boundaries are clearly symmetric around the 45 straight line.
From table 3.2 and figure 3.7, we observe that whenever X3 is strictly positive,
the sum Ax + X*2 + X3 is strictly less than 0.86; that is, strictly less than twice the
throughput of each local LSRAA. This is concluded for two reasons: (a) when
X3 > 0, some percentage of the traffic generated by the boundary MSNs is always
assigned for transmission to a LSRAA already overloaded by local MSN traffic. This
is true because the expected CRI length is upper bounded by window size A if the
algorithm operates in its stability region, and it is slightly larger than A if the system
is temporarily overloaded. Thus, if the rate of the regular local MSN traffic is close to
26


the algorithmic throughput, then the presence of high priority MSNs results in over-
loading of the LSRAA. (b) The rate A3 traffic sometimes uses the window size A that
is optimal for the local LSRAAs, while sometimes it uses the window instead.
This causes throughput reduction even in the absence of regular local MSN traffics.
In fact, in the latter case the maximum such reduction results, because a higher
percentage of the overall system traffic uses then the sub-optimal window size
We point out that the stability regions in table 3.2 and figure 3.7 represent the
case where the traffic is maintained, meaning that no MSNs expire. We also point out
that when traffic is maintained, the collision resolution process induced by the
deployed LSRAAs changes the traffic statistics: that is, when the input traffic is limit
Poisson, the output traffic is not Poisson then, while it maintains the input rate and
can be closely approximated by a Poisson process.
27


Table 3.2 Maximum maintainable Poisson rate window size: A = 2.5599
A3 Ai a;. A*= Ai = \?
0 <0.43 0.43 0.43
0.01 0.429
0.10 0.4288
0.001 0.20 0.4285 0.4278
0.30 0.4282
0.40 0.4280
0.00 0.424
0.01 0.20 0.423 0.42
0.40 0.422
0.00 0.372
0.10 0.370
0.10 0.20 0.368 0.36
0.30 0.364
0.00 0.32
0.10 0.31
0.20 0.20 0.30 0.29
0.30 0.28
0.00 0.260
0.10 0.245
0.30 0.15 0.240 0.23
0.20 0.232
0.00 0.198
0.05 0.190
0.40 0.10 0.180 0.17
0.15 0.170
0.00 0.132
0.50 0.05 0.12 0.11
0.10 0.11
0.00 0.062
0.60 0.01 0.06 0.04
0.02 0.05
For Ax = A2 II O W II O ON 00
28


Figure 3.7 Maximum Maintainable Poisson Rates Window Size: A = 2.5599
29


The 2-channel algorithmic system induces regenerative points within its stability
region. Thus, the regenerative theory, as applied in [26] and [24], is applicable here as
well, for the computation of the expected delays in each of the three subsystems. The
details of this approach can be found in [24]. Figures 3.8 and 3.9 shows the expected
delays for two symmetric systems, with systems' 1 and 2 rates being equal to 0.1 and 0.3,
respectively.
From these figures we observe that the delays of the high priority MSNs are very
little affected by their traffic rate and remain low, while the same delays for the regular
MSNs are significantly increasing as the rate of the boundary traffic increases. From the
latter figures, we decide that: (a) below the (/\.|=A.2=0.1, 7.3=0.1) rate region, the system is
wasteful, and (b) above the (X|=A.2=0.3, A.3=0.05) rate region, the delays of the regular
MSNs are unsatisfactory. Rate region (^i=^2=0.1, A.3=0.1) reflects 0.15 rate per cluster
and 33% of the total MSN population being high priority MSNs. Rate region (X|=A.2=0.3,
7.3=0.05) reflects 0.325 rate per cluster and 7.6% of all MSNs being high priority MSNs.
Referring to the architectural reconfiguration algorithm in chapter 5 and the notation
there, we may initially subsequently select:
V; = 0.15, vu = 0.325, between 0% and 10% high priority MSNs
As we will further discuss in chapter 6, the selection of the v, and vuvalues should
be finally tuned depending on the MSN expiration constants in (3.1).
30


120
Figures 3.8 Expected Delays. Symmetric two-Channel System with Regular
MSN Rates Equal to 0.1
31


50
4^ B Subsystem 1
A Subsystem 2
4 Subsystem 3
35
30
(A
*
O
w 25
20
15
Figures 3.9 Expected Delays. Symmetric two-Channel System with Regular
MSN Rates Equal to 0.3
32


3.4 Numerical Results and Their Evaluation for the Two-Channel System with
Expiration Model
The results of implementing the expiration of the MSN in (3.1) to the two
channel system are exhibited in the next figures. In figures 3.10, 3.12, 3.14, 3.16,
3.18, 3.20 ,3.22, 3.24 ,and 3.26 the expected delays of successfully transmitted
packets are shown, while in figures 3.11, 3.13. 3.15, 3.17, 3.19, 3.21.3.23, 3.25, and
3.27 packet rejection rates are plotted. The figures are the results of simulating the
two symmetric system, with systems 1 and 2 rates being equal to 0.1 with fixed
value for the constant |3 in (3.1) while changing the other constants p and £, with an
increasing order.
From the latter figures, it is observed that in all cases the selection policy in
chapter 3 holds the expected delay of the high priority MSNs at low values, as
compared to the expected delays induced for the regular MSNs; the latter difference
increases, as the rate of the boundary traffic increases.
Form figures 3.10, 3.12, 3.14, 3.16, 3.18, 3.20, 3.22, 3.24 ,and 3.26 it is
noticeable that for a fixed initial energy for the all three subsystems with increasing
energy consumed by transmission, the delay for the high priority MSNs as well as the
regular MSNs decrease. This decrease in the delay is due to the increase in the
expiration rate of the MSNs in (3.1), where the expected delay is defined as the
average delay of those MSNs who has been successfully transmitted. On the other
hand, the same figures exhibit an increase in the average delay as the initial energy
increases for the all thee subsystems with a fixed energy consumed by transmission.
This is due to the fact that if the MSNs are initially equipped with higher energy, then
there will be fewer expirations and thus increased expected delays of the successfully
transmitted traffic.
33


From the first entry rule that the high priority MSNs utilize, it is clear that the
only advantage that they have over the non-high priority MSNs is in their waiting
time before they first enter some CRI. This waiting time is generally lower than that
of the non-high priority MSNs; thus their expected delays are lower than those of the
non-high priority MSNs as well, while they behave exactly as non-high priority
MSNs after they join some CRI. Therefore, for fixed initial energy, as the energy
consumed by transmission increases, the rejection rates of the high priority and the
non-high priority MSNs increase, as shown in figures 3.11,3.13,3.15,3.17,3.19,
3.21, 3.23, 3.25, and 3.27. From the same figures, it is also noticeable that the
rejection rates of the high priority MSNs and the non-high priority nodes decrease, as
the initial energy increases, while the total consumed transmission energy remains
fixed for both.
34


5.6
B Subsystem 1
5.4 A Subsystem 2
O Subsystem 3
^3
Figures 3.10 Expected Delays. Symmetric two-Channel System with
100, p =20, p = 5
35


0.25
0
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
Figures 3.11 Rejection Rates. Symmetric two-Channel System with
5= 100. n = 20, P = 5
36


5.6
B Subsystem 1
5.4 A Subsystem 2
Subsystem 3
Figure 3.12 Expected Delays. Symmetric two-Channel System with
^ 200, r| = 20, p = 5
37


Figure 3.13 Rejection Rates. Symmetric two-Channel System with
5 = 200, ti = 20, (3 = 5
38


10
B Subsystem 1
3
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
^3
Figure 3.14 Expected Delays. Symmetric two-Channel System with
5 = 300, r| = 20, p = 5
39


Figure 3.15 Rejection Rates. Symmetric two-Channel System with
$ = 300, = 20, p = 5
40


5
4.8
4.6
Subsystem 1
Subsystem 2
Subsystem 3
-------0-------0------0
0
3.4
0.1
-15 02 0.25 0.3
0.35 0.4 0.45 0.5
X3
0.55 0.6
relays. Symmetric
^ = 100, rj = 30, p = 5

41


0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
^-3
Figure 3.17 Rejection Rates. Symmetric two-Channel System with
100, ri-30, p = 5
42


7
3.5
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
^3
Figure 3.18 Expected Delays. Symmetric two-Channel System with
^ = 200, r| = 30, p = 5
43


0.12
\z
Figure 3.19 Rejection Rates. Symmetric two-Channel System with
5 = 200, r] = 30, p = 5
44


9
3
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
^3
Figure 3.20 Expected Delay. Symmetric two-Channel System with
^ = 300, r| = 30, p = 5
45


Figure 3.21 Rejection Rates. Symmetric two-Channel System with
^ = 300, r| = 30, (3 = 5
46


4.2
B- - Subsystem 1
4.1 A- - Subsystem 2
e- - Subsystem 3
4
0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
Figure 3.22 Expected Delays. Symmetric two-Channel System with
$=100, ti = 60, P = 5
47


Figure 3.23 Rejection Rates. Symmetric two-Channel System with
^ = 100, r|=60, p = 5
48


5.6
Figure 3.24 Expected Delays. Symmetric two-Channel System with
5 = 200, r\ = 60, p = 5
49


0.24
Figure 3.25 Rejection Rates. Symmetric two-Channel System with
S = 200, r| = 60, p = 5
50


0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6
^3
Figure 3.26 Expected Delays. Symmetric two-Channel System with
^ = 300, p = 60, (3 = 5
51


0.14
B Subsystem 1
Figure 3.27 Rejection Rates. Symmetric two-Channel System with
5 = 300, ti = 60, p = 5
52


4.
The Data Rate Monitoring Protocol
As stated in chapter 2. the architectural reconfiguration algorithm in chapter 5
is facilitated by a high level data rate monitoring protocol. In this chapter, we present
the highlights of the algorithm that implements the latter protocol, as presented and
fully analyzed in [23]. Isolating a single cluster in the system, we first denote by X the
data rate accessing the AFN of the cluster: this data rate encompasses MSN
expirations, whose occurrence is explained in section 3.3. We subsequently decide on
the V/ and vu rate values to be monitored, where 0.15 and 0.325 has been respectfully
selected in section 3.3. The objective is then to decide rate shifts from vu to v; .
Below, we will summarize the generalized algorithm from [23], which monitors shifts
among a set of rates.
The proposed algorithm is sequential, with its operational values updated at
discrete, equally spaced, time instants {Tj}j>0 where the time interval between
consecutive Tjs is a fraction of the life expectancy of MSNs, and it is called a frame.
{Si)i>0 denotes the subsequence of the sequence (Tj}j>0 ,such that, T0 = S0 is the
beginning of time when the system starts operating, and Sj is the ith after So time
instant (corresponding to the beginning of some frame) at which the monitoring
algorithm decides that a shift in the acting rate region has just occurred. Assuming
that, given any fixed rate A,k the cluster data arrival process is stationary, and let
/k(nx,..., nq) denote its q-dimensional distribution in frame lengths; that is.
/[.(n^ ..., nq) is the probability that, in a sequence of q consecutive frames, nt data
arrivals occur in the first frame, and so on, with nq data arrivals finally occurring in
the qth frame, given that the active rate is A* throughout. Assuming that the
distributions {/k(n1( ...,nq) ) are well-known for all ks (or all A,ks).
53


Then, we propose the following sequential data rate monitoring algorithm, from [23],
which traces consecutive data rate shifts.
4.1. The Algorithmic System
1. The monitoring algorithmic system is designed at the central rates {X^^n .
2. Let at some Sj the rate Xk be decided as just starting, by the monitoring
algorithmic system. Then, immediately at Sj, a set of n 1 parallel algorithms starts
operating. The jth such algorithm is monitoring a possible shift from the rate Xk to the
rate Xj where Xk ^ Xj .sequentially, with adaptations occurring at beginnings of
frames. The n 1 parallel algorithms use a reflective threshold at zero and a common
decision threshold qk Let Vkj(0) denote the operating value of the algorithm
monitoring a (Xk > Xj} shift at Sj when it starts operating; let Vkj(r) denote its
operating value at its rth adaptation step. Then, the operating values of the algorithm
are sequentially updated as follows:
vkj(0) = 0
Vkj(r + 1) = max(0,Vk|(r) +
(4.1)
Si+1 is then the first time after Sj that one of the above n 1 algorithms first crosses
the common decision threshold r|k. If the latter algorithm is the one which monitors a
Xk > Xp shift, a set of n 1 parallel algorithms, each monitoring a shift from Xp to
one of the remaining rates, becomes initialized. The latter algorithmic system has
operational characteristics as those stated above, utilizing a common decision
threshold r| .
A summary of the performance characteristics of the algorithm, taken from
[23], is included in Appendix B. The algorithm induces correct decisions as well as
54


false alarms whose relative relationship is controlled by the value of the selected
decision threshold.
When the data rate monitoring algorithm is deployed for both architectural
reconfiguration purposes and dynamic routing adaptations, as in [23], then, multiple
rates are monitored and multiple parallel algorithms are simultaneously operating, as
stated above. When focusing solely on the architectural reconfiguration problem, the
data rate monitoring per cluster is implemented by a single algorithm as in (4.1) that
monitors vu to vL possible shifts.
Figure 4.1 depicts the time evolution of the two channel monitoring system
for threshold value 1000. The solid and dashed lines represent the time where the
threshold crossed for channel one and two respectively.
55


1200
1000
V channel 1
u!
V channel 2
Ul
n channel 1
. channel 2
<1)
(U
>
76
c
o
800
600
<1)
CL
O
400
200
0
0 500 1000 1500 2000 2500 3000 3500
Slots
Figure 4.1 Time Evolution of the Two-Channel Monitoring Algorithmic
System.
56


Figure 4.2 illustrates the relationship between the threshold value and the
power and false alarm curves for vu > v; algorithm for different threshold choices.
By viewing the latter figure, it is plain to see that as the value of the decision
threshold increases, the false alarm curve decreases, but so does the power curve. The
threshold selection for the u to / change monitoring algorithm may be based on a
required lower bound for the power and a required upper bound for the false alarm, at
a given time instant tn. From the same figure we observe the better performance for
the threshold value 1000 and especially for time values below 40.
1
0.9
0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0
// Fa!se(700)
Power(700)
. *. False(900)
Power(900)
. Fa!se(1000)
Rower(IOOO)
False(2000)
\ Power(2000)

*



20

40
60
80
100
Figure 4.2 False Alarm and Power Curves for the u to l Monitoring
Algorithm.
57


4.2 The Algorithm for the Poisson
As explained in chapter 2. the data generated by the MSNs in cluster i may be
modeled as cumulatively comprising a homogeneous limit Poisson process, with rate XCl
bits/time unit. As stated in section 3.3, the traffic accessing the AFN of the cluster, while
not Poisson then, it can be closely approximated by a Poisson process. The Poisson
arrival process is memoryless: the conditioning in the log-ratio updating step of the
algorithm is (4.1) then drops. If d denotes the length of a frame in time units, the
(Ak - Aj) monitoring algorithm in (4.1) takes the following form:
vkj(0) = 0
Vkj (r + 1) = max (o, Vkj (r) + d
kk-kj + nr+1log(^)])
(4.2)
Where nr+1denotes the number of data departures within the (r + l)thframe from the
beginning of the (Xk lj) monitoring algorithm. Let us define
/, \ ii
- [^-k ~ ^j]
log
(4.3)
where min(A.k,kj) < ^(A,k, A,j) < max(Xk, A.j). We may select {kj} rates such that
kj) are rational numbers for all k and j, and we then define the integers tkj and
skj tkj < skj as follows:
<(VAi) = r (4-4>
bkj
The algorithmic thresholds can then all be selected as positive integers, and without
lack in generality, the algorithmic adaptation in (3) can be transformed as follows:
Vkj(r + 1) = max{0,Vkj(r) + (-l)ime(kT[ skjnr+1 dtkj]} (4.5)
fO; if Aj > kk
Where ime(k.j) = j1; ia 58


4.3 Numerical Results and Their Evaluation for the Two- Channel
Monitoring Algorithmic Systems.
We simulated the two channel system for the total per cluster traffic rate being
the as selected above vu and for the high priority traffic being between 0% and 10%
of the per regular traffic. We monitored the input to the two AFNs traffics deploying
the high level monitoring protocol for the monitored upper and lower rates bounds,
selected frame lengths, and for various values of the constants p, and P of the
expiration model in section 3,2. The performance metrics computed were packet
rejection rates, distribution and the expected delays of the non expired MSNs.
The frame lengths selected is equal to 11 time units, the integers t^ and s^j in
(4.4) were selected equal to 11 and 50 respectively. Following the threshold selection
technique explained in section 4.1; all the algorithmic decision thresholds were
selected equal to 1000 units.
Figures 4.3 and 4.4 are the results of evaluating the two channel monitoring
system for the constants 1; =100, q =50, and P =10 of the expiration model in section
3.2. In these figures packet rejection rates and the delay distribution of the
successfully transmitted packets are plotted, in the case where the algorithm induced
correct decision. The results of the latter figures show an increase in the rejection rate
of the three subsystems with time, which may result in a rate drop below the
acceptable lower bound.
59


0.5
Figure 4.3 Rejection Rates. Two Channel Monitoring Algorithmic System
^ = 100, r| = 50, (3 = 10
60


5000
Subsystem 1
5000
4000
3000
2000
1000
0
2
Subsystem 2
10
12
14 16 18
Subsystem 3
400
Figure 4.4 Packet Delay Distributions. Two-Channel Monitoring Algorithmic
System 2; = 100, r| = 50. P = 10
61


6
5
4
3
2
1
0
9
Subsystem 1
9
Subsystem 2
9
Subsystem 3
1 2 3
Node group index
Figure 4.5 Expected Delays. Two-Channel Monitoring Algorithmic System
^ = 100, p = 50, p = 10
62


To show the effectiveness of the proposed monitoring algorithm, the same
design parameters of the monitoring algorithm were used to evaluate the two-channel
monitoring algorithmic system for two different sets of parameters in the expiration
model. Based on the obtained results, we notice that the rejection rate in both of the
channels converges to values that may not fall below the acceptable per cluster lower
limit. The results also suggest that the rejection rate increases as the constants of the
expiration model increase in value.
From the results in figures 4.5, 4.8, and 4.11, we also notice that the dynamic
selection policy in chapter 3 effectively controls the expected delays for subsystem
three, uniformly, maintaining them at values lower than those in subsystems one and
two.
63


Figure 4.6 Rejection Rates. Two-Channel Monitoring Algorithmic System
S=100,ri = 10, p = 5
64


4000
Subsystem 1
Subsystem 2
4000
Subsystem 3
800
Figure 4.7 Packet Delay Distributions. Two-Channel Monitoring Algorithmic
System ^ = 100, rj = 10. P = 5
65


18
16
14
12
10
8
6
4
2
0

Subsystem 1
Q
Subsystem 2

Subsystem 3
1 2 3
Node group index
Figure 4.8 Expected Delays. Two-Channel Monitoring Algorithmic System
5 = 100, r| = 10, p = 5
66


0.25
subsystem 1
subsystem 2
Figure 4.9 Rejection Rates. Two Channel Monitoring Algorithmic System
2; = 200, t) = 30, P = 10
67


4000
Subsystem 1
Subsystem 2
4000
Subsystem 3
600
Figure 4.10 Packet Delay Distributions. Two-Channel Monitoring Algorithmic
System ^ = 200, r] = 30, (3=10
68


16
14
12
10
8
6
4
2
0
0
9
Subsystem 1
O
Subsystem 2
9
Subsystem 3
1 2 3
Node group index
Figure 4.11 Expected Delays. Two-Channel Monitoring Algorithmic System
= 200, r] = 30, P = 10
69


5. An Architectural Reconfiguration Algorithm
As discussed in chapter 3, the allowable values of the cluster data rates {Ac;} in
the network are determined by the throughput /delay characteristics of the
transmission Random Access (RA) algorithms deployed in the clusters. Specifically,
given the cluster transmission RA algorithm, the highest allowable cluster data rate
should be such that the induced delays and retransmissions are non-detrimental to the
network mission, in the sense of causing the expiration of an unacceptable percentage
of MSNs. We note that algorithmic delays induced by RAs are dependent on their
algorithmic throughput. Thus, the cluster data rates {Aq} are all bounded from above
by bounds determined by the characteristics of the per cluster deployed transmission
protocols from the MSNs to the corresponding AFN.
In addition, as induced by the deployed transmission algorithm, when the
data rate in a cluster drops below a certain level, the existence of the cluster becomes
wasteful, due to the then unnecessary induced increase in the size of the backbone
network. Assuming that the transmission RA protocol per cluster is fixed, identical
for all clusters and known, let us denote by vt and vu the common determined lower
and upper bounds to each cluster data rate, respectively. If the aggregate data rate
from all MSNs in the overall network is denoted Ac the smallest possible number of
clusters in the network is then[Ac / vu], while the largest such number is then
[Ac / vd
We will assume that a rate monitoring algorithm is deployed at the AFNs.
When the data rates in all clusters remain within the (vt, vu) range, then, detected
data rate changes dictate only rate reallocations in the backbone network of the
overall structure, without any imposed architectural reconfigurations, as in [23].
When, instead, some cluster data rates fall outside the (v,, vu) range, then,
70


architectural reconfigurations are first imposed, dictated by an architectural
reconfiguration algorithm, followed by data rate reallocations on the new backbone
network topology, as dictated by the deployed routing algorithm. In this chapter, we
focus on the architectural reconfiguration algorithm.
5.1. The Algorithm
The original overall network architecture is based on the aggregate network
data rate Ac and the upper and lower rate bounds vu and v( determined by the
transmission protocols in the clusters. In particular, assuming that transmission range
is not a limiting factor in the geographical region covered by the network, |AC / vu]
AFNs are originally deployed, each heading a cluster of MSNs with equal cluster data
rates {A^}. The latter number of AFNs selected minimizes the size of the backbone
network, subject to the rates per cluster remaining within the target range(v;, vu);
thus it minimizes routing complexities and delays as well as network propagation
delays. When the data rate monitoring algorithm detects that one or more cluster data
rates fall outside the (v;, vu) range, the architectural reconfiguration algorithm is
initiated.
Let {Rj}i>0 denote the sequence of time instants when network architectural
reconfigurations are initiated, where Ro denotes the time when the original network
architecture is deployed, based on the principles stated in the above paragraph. Let
{Ac(l)).>o be the aggregate network data rates at the instants {Rj}j>o respectively,
where Ac*-0-1 = Ac. Assuming no MSN replacement during the time when the network
objective is satisfied, the sequence of rates in {Ac^}. are monotonically non-
increasing with increasing index i. According to the above notation, Rj denotes the ith
time when the data rate monitoring algorithm detects that one or more cluster data
71


rates fall outside the (v,, vu) range. At Rj, the architectural reconfiguration
algorithm implements the following steps:
Step 1: The aggregate network data rate Ac('1^ and subsequently |A.c^/vuj are
computed.
Step 2: (a) If |Ac^Vvu] = [Ac(-1""1VvuJ > then, as compared to the network
architecture at time Rj_l5 the architecture of the backbone network remains
unchanged, while the MSNs are reallocated to formulate rate-equivalent clusters. The
reallocation is initiated by the BS, broadcast to the MSNs by the AFNs, and
implemented by each MSN independently via equiprobable selection among the
active clusters. For the high priority MSNs, the equiprobable selection will be among
cluster groups, instead, as explained in chapter 4. We note that MSN reallocation may
be judged as inappropriate in cases where it may cause unacceptable increase in MSN
extinction rate. This issue will be further discussed in chapter 6.
(b) If [Ac(l)/vuJ < [Ac^1-1Vvu] then some clusters are eliminated: The
clusters are first ranked according to their aggregate local data rate, and
[A.ch-1)/vuJ [Ac^/vyj clusters possessing the lowest such rates are eliminated.
The survived AFNs are decided upon by the BS and become known to the MSNs via
broadcasting. The MSNs are then reallocated among the survived clusters, for rate-
equivalence. The implementation of the reallocation is as in (a).
72


5.2 Numerical Results and Their Evaluation for the Architectural
Reconfiguration Algorithm.
In the simulation, a complete environment comprised of the LSRAA for K=3,
the monitoring protocol, and the reconfiguration algorithm, is developed to validate
the proposed architectural reconfiguration algorithm. The two channel system was
simulated for the total per cluster traffic rate being selected above the upper bound vu,
and for the high priority traffic being between 0% and 10% of the per cluster total
rate. The high level monitoring protocol in chapter 4 was used to monitor the input to
the two AFNs traffics, and the architectural reconfiguration algorithm was
subsequently implemented, as dictated by the decisions induced by the monitoring
algorithm. The performance metrics computed were packet rejection rates, as well as
delay distributions and expected delays of the non expired MSNs.
To evaluate the performance characteristics of the proposed algorithm, the
algorithm is applied on the same set of parameter values of both the monitoring
algorithm and the MSN expiration model, as those used in section 4.2.
Figure 5.1 shows an increase in the rejection rates of all three subsystems of
the two-channel system. The latter increase is due to fact that a vu > v; shift in
channel one has been detected and. as a result, the system reconfigured itself. The
reconfiguration triggers a retransmission process throughout the total MSN
population, which, in return, induces increased rejection rates throughout the whole
system. We will elaborate upon these concepts in chapter 6.
73


0.8
Figure 5.1 Subsystems Rejection Rates
7 4


The delay distribution of the nonexpired MSNs in the three subsystems is
shown in figure 5.2, where it is noticeable how the distribution of subsystem three is
concentrated more around smaller values, as compared to subsystems one and two. In
addition, figure 5.3 shows the consistent effect on the expected delays of the three
subsystems. Due to the increase in the rejection rates, the expected delay for the three
subsystems uniformly decreases. From both figures 5.2 and 5.3, it is evident that the
selection policy in chapter 3 maintains the delays of subsystem three at values lower
than those in subsystems one and two.
In the case where the detected data rate changes in both the channels are
within the vu > v; range, the architectural reconfiguration algorithm in section 5.1
will implement only step 2 (a) and the system performance will be the same as
exhibited in figures 4.6 to 4.11. The monitoring algorithm in section 4.1 induces false
alarms as well as correct decisions, therefore in the case that the algorithm
erroneously detects a rate change in one of the channels, step 2 (b) of the architectural
reconfiguration algorithm erroneously follows, while the rate in the channel has not
been reduced below the lower bound to necessitate such reduction. Then, the
erroneously decided cluster elimination will result in unnecessary traffic overloading
of the survived channel. These issues will be further discussed and analyzed in
chapter 6.
75


2500
Subsystem 1
2000
1500
1000
500
0
2
Subsystem 2
3000
16
14 16
Subsystem 3
400
Figure 5.2 Subsystems Delay Distribution
76


7
6
5
4
3
2
1
0
0
o
Subsystem 1

Subsystem 2
9
Subsystem 3
1 2 3
Node group index
Figure 5.3 Subsystems Expected Delays
77


5.3 A Specific Experimental Scenario
In this section, we investigate the two-channel monitoring algorithmic system
in the case where the high priority MSNs is equipped with higher initial energy than
that of the local MSNs. In this case, the results show the expected decrease of the
rejection rate in subsystem three. The results also show that the selection policy
maintains the expected delay for subsystem three at lower values than those for
subsystems one and two, but, as the difference between the initial energy levels of the
subsystems increases, the expected delay of subsystem three increases as well, since,
then, a larger number of admitted high priority packets contribute to increased packet
processing load.
Figure 5.4 Rejection Rats for locals =100, ^highpriority =130, r\ -50, and (3 -10
78


400
Subsystem 1
300
200
100
0
3 4 5 6 7
3000
Subsystem 2
2000
1000
0
2
16
Subsystem 3
3000
Figure 5.5 Delay Distributions for ^ocais 100, ^highpriority =130, r| =50, and P =10
79


7
6
5
9
9
9
4
3
2
1
0
0 12 3
Node group index
Figure 5.6 Expected Delay for ^iocais =100,^highpriority=130, r| -50,and (3 -10
80


0.8
Figure 5.7 Rejection Rats for ^locals =100, ^highpriority =200, ti =50, and p =10
81


2500
Subsystem 1
2000
1500
1000
500
0
3 4 5 6
7
Subsystem 2
2000
Figure 5.8 Delay Distributions for locals =100. ^highpriority =200, r\ =50, and |3 =10
82


7
6
5
9
9
4
3
2
1
0
0 12 3
Node gruop index
Figure 5.9 Expected Delay for ^ocals =100, ^highpriority =200, rj =50, and (3=10
83


6. Overall System Issues
As induced by the architectural reconfiguration algorithm in chapter 5, when a
vu vi shift is detected by at least one of the cluster data rate monitoring high level
protocols, the overall system reconfigures itself, where all MSNs reselect the AFN(s) that
they will be connected to for their transmissions. This reselection halts the transmission
process, until reconfiguration of the clusters is completed, causing interruptions of those
transmissions that are in progress at the time of the halting. The latter transmissions need
to be restarted by the corresponding MSNs, resulting in additional delays and
retransmissions that may exceed the limit imposed by the low energy MSN characteristic,
(see section 3.3). Thus, architectural reconfiguration may cause increased MSN
expiration rates.
The so caused MSN expiration rate increase may be reduced if, step 2(a) of the
Architectural Reconfiguration Algorithm in section 5.1 is modified, so that no cluster
reselection by the MSNs occurs then; that is, in the case where vu - v( rate shift in one
or a few clusters does not change the number of clusters in the system, the MSNs remain,
instead, with the AFN(s) they were associated with before data rate shifts were detected,
and do not interrupt any transmissions in progress. In the latter case, however, the overall
system is not balanced; MSNs that are located in relatively overloaded clusters will suffer
higher delays in their future transmissions, since they are not allowed to reallocate, at the
risk of exceeding their life-span.
In summary, maintaining step 2 in the Architectural Reconfiguration Algorithm,
as described in chapter 5 versus modifying it to exclude MSN reallocations induces a
tradeoff between MSN expirations due to transmission interruptions and MSN
expirations due to delays in relatively overloaded clusters. Given a specific clustered
sensor environment, this tradeoff needs to be numerically evaluated, before a final
84


decision regarding MSN reallocations in step 2 of the Architectural Reconfiguration
Algorithm is made.
The false alarms induced by the data rate monitoring algorithm in chapter 4 may
occasionally dictate erroneous cluster reconfigurations and subsequent backbone network
reductions. In particular, the monitoring algorithm may erroneously lead to the step 2(b)
case of the architectural reconfiguration algorithm in section 5.1, imposing elimination of
some clusters, while the actual overall network data rate Ac has not been sufficiently
reduced to necessitate such reduction. Implementation of cluster elimination will then
result in traffic overloading of some clusters, with subsequent increase of the MSN
expiration rate in these clusters. The latter expiration rate increase must be evaluated
against such increase due to the excessive routing and propagation delays in the non-
reduced backbone network, for the subsequent adjustment of the data rate monitoring
decision threshold, in harmony with the per cluster boundary rates (v;, vu).
Given a member of the LSRAA class in chapter 3, given the upper bound vu of
the maintained data rate per cluster, given the MSN-expiration formula in (3.1), a specific
value of the MSN expiration rate is induced. When the latter value is subtracted from vu,
the result should be bounded from below by the data rate lower bound v(. In addition, if it
is desirable that the MSN expiration rate, solely due to (3.1), be upper bounded, then, an
upper bound to the value of vu is induced. As a conclusion, the pair (v,, vu) of rate
values is dependent on the MSN-expiration formula in (3.1).
85


7.
Conclusion
We considered clustered sensor network topologies containing a percentage of
sensors that generate high priority data. A specific random access transmission
protocol per cluster was deployed that facilitates the high priority data, where the
protocol induces coupling between different transmission channels. To model the
expiration of the life-limited nodes, we selected a linear expression, as function of
retransmission attempts and channel monitoring time lengths, where node expiration
causes changes in the cluster data rates, and thus induces dynamics in rate allocations
and network architectural configurations.
We studied the system of two coupled channels, first in the absence of the
expiration model, to determine the allowable values of the cluster data rates in the
network, where the vz and vu values were chosen as the uniformly acceptable per
cluster lower and upper data rate bounds, respectively. The behavior of the two
channel system was also studied in the presence of the expiration model, via
extensive simulations and for various values of the constants involved in the latter
model. The results demonstrated quantitatively the following qualitative effect: as
the due to nodes expirations rejection rate increases, the expected delay of the
survived nodes decreases, while, at the same time, the proposed deployed random
access protocol maintains the expected delay of the high priority data at values lower
than those for the non-high priority data.
To detect vu to v( possible shifts in cluster data rates, a rate monitoring
algorithm was deployed independently at each AFN to detect such changes and to
subsequently communicate them across the AFNs. The performance of the
monitoring system was analyzed and evaluated, where it was found that the
monitoring system performs with accuracy and efficiency in detecting the rate shifts.
86


As induced from the operation and the performance characteristics of the
deployed transmission protocol, when the data rate in a cluster drops below a certain
level, the existence of the cluster becomes wasteful, due to the then unnecessary
induced increase in the size of the backbone network. The implementation of the
latter elimination process was implemented by the proposed architectural
reconfiguration algorithm that is facilitated by the rate monitoring algorithm.
The implementation of the proposed architectural reconfiguration algorithm was
illustrated by developing a complete environment comprised of the LSRAA for K=3, the
monitoring protocol, and the reconfiguration algorithm. The results showed that the
architectural reconfiguration may cause increased MSN expiration rates, where the latter
expiration rate increase must be evaluated against such increase due to the excessive
routing and propagation delays in the non-reduced backbone network.
To gain further insight into the performance of the system, we studied the case
where the high priority MSNs has higher initial energy than that of the local MSNs. The
results showed that as the difference between the initial energy levels of these subsystems
increases, the expected delay of the high priority subsystem increases as well, while it is
maintained at values lower than those of the non-high priority subsystem.
From the analytical and performance evaluation results, we expect that the
proposed algorithms and protocols, being dictated by the objective of the sensor networks
and their environment, will have a significant impact on the design, the performance
monitoring and the dynamic reconfiguration of mobile sensor networks used in a variety
of applications. We also expect that our proposed monitoring system may be modified to
detect system anomalies efficiently, to allow for pertinent system adaptations and, thus,
further system performance enhancement.
87


APPENDIX A
Algorithmic Analysis of the Two-Channel System
Consider either one of the local LSRAAs, whose operations are described in
section 3.1. Let us select the 3-Cell algorithm among those in the class in [12].
Consider some CRI within the system of the LSRAA, which starts with transmissions
from packet arrivals in an arrival interval of cumulative length u. We will call u, the
"length of the examined interval". Let us then define:
E{ i |u} : Given that the length of the examined interval is equal to u, the expected number of
slots needed for its resolution; that is, for the successful transmission of all the arrivals in the
examined interval.
Let Lk denote the expected length of a CRI given that it starts with a collision of
multiplicity k. We can then write:
Since E{ / |u, k} = Lk depends only on k. In [12], and focusing on the 3-cell algorithm, it
is shown that
1. Lk; k > 0 can be computed recursively, and
2. Lk are quadratically upper-bounded.
As found in [12], in the presence of the limit Poisson user model, each local LSRAA
has then a throughput of 0.43, attained for window size A*= 2.5599. Thus, in view of the
system considered in this thesis, the Poisson intensities Xj, j = 1,2,3 must satisfy the
following necessary conditions, for overall system stability:
k
(A.1)
^ < 0.43, and X2 < 0.43, and + X2 + L3 < 2(0.43) = 0.86
(A.2)
88