Switching in sequential tree networks

Recursive analytical expressions for speedup and solution time for a multilevel tree sequentially processing a divisible load under cut through switching are developed. Such cut through switching is shown to be more efficient than store and forward switching. Aerospace applications include sensor networks, radar, and satellite imagery processing.     

Wireless sensor networks: scheduling for measurement and data reporting

An optimal load allocation approach is presented for measurement and data reporting in wireless sensor networks with a single level tree network topology. The measurement problem investigated involves a measurement space, part of which can be sampled by each sensor. We seek to optimally assign sensors part of the measurement space to minimize reporting time and energy usage. Three representative measurement and reporting strategies are studied. This work is novel as it considers, for the first time, the measurement capacity of processors and assumes negligible computation time which is radically different from the traditional divisible load scheduling research to date. Aerospace applications include satellite remote sensing and monitoring and sensor networks deployed and monitored from the air.     

Distributed computation for a tree network with communicationdelays

Tree networks of communicating processors are examined with the objective of solving a computational problem in a minimal amount of time. The processors in the networks may be equipped either with or without front-end processors for communicating of loading. The determination of the optimal division of processing load is discussed for the network with and the network without front-end processors. The inclusion of solution time, the time taken for sensors to report the solution back to originator, is discussed     

Optimal time-varying load sharing for divisible loads

A load sharing problem involving the optimal load allocation of divisible loads in a distributed computing system consisting of N processors interconnected through a bus-oriented network is investigated. For a divisible lend, the workload is infinitely divisible so that each fraction of the workload can be distributed and independently computed on each processor. For the first time in divisible load theory, an analysis is provided in the case when the processor speed and the channel speed are time varying due to background jobs submitted to the distributed system with nonnegligible communication delays. A numerical method to calculate the average of the time-varying processor speed and the channel speed and an algorithm to find the optimal allocation of the workload to minimize the total processing finish time are proposed via a deterministic analysis. A stochastic analysis which makes use of Markovian queueing theory is introduced for the case when arrival and departure times of the background jobs are not known     

Performance limits for processor networks with divisible jobs

Ultimate performance limits to the aggregate processing speed of networks of processors that are processing a divisible job are described. These take the form of either closed-form expressions or numerical procedures to calculate the equivalent processing speed of an infinite number of processors. These processors are interconnected in either a linear daisy chain with load origination from the network interior or a tree topology. The tree topology is particularly general as a natural way to perform load distribution in a professor network topology with cycles (e.g., hypercube, toroidal network) is to use an embedded spanning tree. Such limits on performance are important as they provide an ideal baseline against which to compare the performance of finite configurations of processors.     

Processor equivalence for daisy chain load sharing processors

A linear daisy chain of processors in which processor load is divisible and shared among the processors is examined. It is shown that two or more processors can be collapsed into a single equivalent processor. This equivalence allows a characterization of the nature of the minimal time solution, a simple method to determine when to distribute load for linear daisy chain networks of processors without front end communication subprocessors and closed form expressions for the equivalent processing speed of infinitely large daisy chains of processors     

On applying the extended Kalman filter to nonlinear regressionmodels

In using an extended Kalman filter to estimate the parameters of a nonlinear regression model, the order in which the measurements are processed can be important, as the filter cannot always be expected to produce a satisfactory global fit when processing the measurements in the causal order in which they occur. To obtain a better fit, the possibility is explored of using a sequential state estimator in an offline mode to process the measurements in a random order rather than in the causal order in which they occur     

Layernet: a self-organizing protocol for small ad hoc networks

A self-organizing protocol is proposed for small ad hoc networks. Among this protocol's original features is the initial creation of an asynchronous sparse tree topology followed by a transition to a more fully connected network and synchronous scheduling. An efficient address bundling technique and unique reliability simulation results for this protocol are also presented     

Optimal divisible job load sharing for bus networks

Optimal load allocation for load sharing a divisible job over N processors interconnected in bus-oriented network is considered. The processors are equipped with front-end processors. It is analytically proved, for the first time, that a minimal solution time is achieved when the computation by each processor finishes at the same time. Closed form solutions for the minimum finish time and the optimal data allocation for each processor are also obtained     

Equal allocation scheduling for data intensive applications

A new analytical model for equal allocation of divisible computation and communication load is developed. Equal allocation of load is attractive in multiple processor systems when real time information on processor and link capacity that is necessary for optimal scheduling is not available. The model includes a detailed accounting of solution reporting time. Equal allocation scheduling is compared with sequential scheduling and a new type of multi-installment scheduling. Aerospace applications include the processing of satellite imagery, radar, and sensor networks.