Citation |

- Permanent Link:
- http://digital.auraria.edu/AA00004020/00001
## Material Information- Title:
- Dynamic architecture-reconfiguration algorithms and transmission protocols for clustered sensor network topologies with prioritized data
- Creator:
- Salem, Fatma S
- Publication Date:
- 2011
- Language:
- English
- Physical Description:
- xii, 103 leaves : ; 28 cm
## Thesis/Dissertation Information- Degree:
- Master's ( Master of Science)
- Degree Grantor:
- University of Colorado Denver
- Degree Divisions:
- Department of Electrical Engineering, CU Denver
- Degree Disciplines:
- Electrical Engineering
- Committee Chair:
- Papantoni, Titsa
- Committee Members:
- Bialasiewicz, Jan
Fardi, Hamid
## 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 )
## Auraria Membership |

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 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 |