Hirsch M.J., Pardalos P.M., Murphey R. Dynamics of Information Systems: Theory and Applications

Подождите немного. Документ загружается.

116 A. Murgu et al.

The nondegenerate cases where the optimal solution (5.26)–(5.28) is attained by

a solution of (5.33) with all corresponding weighting coefﬁcients strictly positive,

will be considered in the following development. In degenerate cases where the

optimal solution of (5.26)–(5.28) is attained by a solution of (5.33) with one or more

weighting coefﬁcients equal to 0, two or more objective functions J

, i =1, 2,...,k

in problem (5.31) do not conﬂict with each other in the neighborhood of the optimal

solution of problem (5.26)–(5.28).

5.4.2 Distributed Implementation

Motivated by sustainable and maintainable information retrieval functionality which

collects all the QoS related data (e.g., usage utility, capacity, bandwidth, CPU and

memory consumption, current numbers of application running), we adopt a hier-

archical server-client architecture as shown in Fig. 5.5. When more than one path

satisfying the bandwidth demand exists, the information management system helps

the selection of the path minimizing the blocking probability of future reconﬁgu-

ration requests [15]. The connectivity request is processed independently at each

network node, based only on the node identiﬁer which is carried in the connectivity

request signal. When network resources are not available on such shortest paths, the

quality of service degrades. Resource Reservation Protocols allow the signaling and

instantiation of the channel trails in a path oriented networking environments [16].

Dynamic reconﬁguration can be explicitly or implicitly triggered. In the former,

the reconﬁguration process is initiated through an invocation to the allocate method,

while implicit reconﬁguration starts when the reconﬁguration controller detects that

Fig. 5.5 Reconﬁguration Controller information patterns

5 Topology Information Control in Feedback Based Reconﬁguration Processes 117

a required network element is not invoked. The invocation sequence for explicit re-

conﬁguration is the following: (1) RC looks up for the requested network element

identity in the known object table; (2) Resource Reservation Protocol generates a

new conﬁguration request; (3) if the request has a persistent trail, the RC transfers

the serialized state from the lookup table to the element; (4) RC activates the net-

work element (start invocation); (5) RC updates the network element in the location

service.

Proposition 4 If the optimal solution of problem (5.26)–(5.28) is attained by a non-

inferior solution with all corresponding weighting coefﬁcients strictly positive, the

following optimal condition must be satisﬁed:

∂J/J

p−1

∂J/J

p−1

=···=

∂J/J

p−1

(5.40)

Proof Since the tangent space S at the noninferior solution that attains the opti-

mal point of problem (5.26)–(5.28)isa(k −1)-dimensional hyperplane, we know

from Proposition 3 that the vector [1,λ

,...,λ

] constitutes the basis of a one-

dimensional space S

∗

which is the orthogonal complementary space of S. Equation

(5.35) can be rewritten as





i=1



∂J



∂J

∂λ





=λ





i=1



∂J

∂λ





=0,j=2,...,k

(5.41)

Note that the vectors [∂J

/∂λ

,...,∂J

/∂λ

]

, j =2,...,k, constitute the (k −

1)-dimensional basis for tangent hyperplane S, we conclude from (5.41) that the

optimal solution of problem (5.26)–(5.28) is the vector



∂J/∂J

,...,∂J/∂J





∂J/∂J

p−1

,...,

∂J/∂J

p−1



(5.42)

belongs to the one-dimensional orthogonal complementary space of the tangent hy-

perplane S when all weighting coefﬁcients are strictly positive. Equation (5.30)

holds since the vectors [1,λ

,...,λ

] and [∂J/∂J

p−1

,...,∂J/∂J

p−1

] are

proportional. 

Proposition 4 provides a necessary condition for implementing the optimal value

of weighting vector λ. The weighting vector λ is viewed as the signaling infor-

mation that occurs among the cooperating agents involved in controlling the net-

work connectivity. Let J

(λ

), i =1,...,k, be the optimal solution generated by the

weighting pth power Lagrangian formulation with weighting vector λ

at iteration t.

The gradient of the objective function at point [J

(λ

),...,J

(λ

)] in the objective

space is given by

∇J







∂J/∂J

,...,∂J/∂J



|λ



∂J/∂J

p−1

,...,

∂J/∂J

p−1



|λ

(5.43)

118 A. Murgu et al.

It is known from Proposition 3 that the vector



1,λ

,...,λ



(5.44)

is a normal vector on the noninferior frontier at point [J

(λ

),...,J

(λ

)] in the

objective space. The projection of the negative gradient −∇J on the tangent hyper-

plane at the current noninferior point can be calculated by

J (λ

) =



J





,...,J





=−∇J





+J





λ



(5.45)

where λ

 is the norm of vector λ



=1 +



i=2





(5.46)

From the Cauchy–Schwarz inequality, we have

∇J





∇J





=−



∇J







∇J







≤0 (5.47)

We further need a way to adjust the value of the weighting vector λ in order to

achieve the improvement in the objective space {J

,...,J

}. The tangent hyper-

plane at point [J

(λ

),...,J

(λ

)] is of dimension (k −1), so only (k −1) of the k

terms J

(λ

) in (5.45) are independent. The following ε-constraint problem can

be formulated to realize the descent direction

minJ

(5.48)

subject to J

≤J





+αJ





,j=2,...,k (5.49)

where α is a step size parameter which can be adjusted on line to guarantee a decre-

ment of the overall objective function J . The dual function of (5.48)–(5.49)is

H(λ)=minJ



j=2



−J





−αJ





(5.50)

subject to (5.47) and (5.48). The descent direction [J

(λ

),...,J

(λ

)] at it-

eration t + 1, needs the new values of λ

, i = 1,...,k, which can be obtained

through maximizing the dual function with respect to λ at current noninferior point

(λ

),...,J

(λ

)]. The derivative of the function H(λ) with respect to λ

at the

current point [J

(λ

),...,J

(λ

)] is

∂H(λ)

∂λ

=−αJ





,j=2,...,k (5.51)

5 Topology Information Control in Feedback Based Reconﬁguration Processes 119

The value of λ is the gradient control process algorithm

t+1

=λ

∂H(λ)

∂λ

=λ

−αJ





,j=2,...,k (5.52)

The dual function H(λ

t+1

) in (5.50) is equivalent to the following weighted pth

power Lagrangian problem for a selected λ

t+1

min J



j=2

t+1

(5.53)

This sets the weighted pth power Lagrangian formulation with an updated value of

λ at iteration t +1 for the lower level.

The main purpose of the system-level reconﬁguration is to provide transparency

(for location, access, transport mechanism). Location transparency allows clients

to invoke service requests without any prior knowledge of the real location of the

service. This is of special interest in dynamic reconﬁguration environments, since

the reference (address assigned in the network information map) of a reconﬁgurable

component can be deferred to the instantiation inside a certain reconﬁgurable area,

at runtime. The location service, then is in charge of providing a valid endpoint

(the address where the instantiated component is located) when a client requests the

location of concrete service [17].

Two entities are involved in the location process. The proxy stores a reference

for the locator object, instead of a static endpoint to the server hardcoded at design

time. On the other side, the location service (or directory service), provides the

valid endpoint from the requested networked element identity. When an invocation

is received from the client network element, the proxy will ﬁrst request the current

location of the remote element (using the object identiﬁer). The location service

contains a location table where object identities are linked with valid endpoints.

Once the location is obtained, the networked element will perform a second request:

the real invocation. However, the indirection doesn’t necessarily imply two requests

per invocation. That can be easily avoided simply caching the obtained location. The

interface for the locator object has two kind of methods. The locate method provides

the location functionality previously described [18].

Another problem in the dynamically reconﬁgurable environments is that the need

for information processing may be difﬁcult to predict at design time. Bitstreams

for new networked element types may be deployed at any time, and extra unpre-

dictable space is also needed for state storage of object instances with persistence

capabilities. The solution is to deﬁne a dynamic memory allocation service that will

transparently provide basic primitives for information management. The service is

provided by an specialized object called the Allocator. The Allocator has two main

characteristics. On one side it centralizes information management for the whole

system. On the other side it offers a well-known interface, completely independent

from the implementation technology or information hierarchy. The service interface

is based on two methods. The allocate method requests the allocation of a certain

120 A. Murgu et al.

memory block size, while the release method frees the information block. The return

value for the allocate method is a proxy to network information map.

5.4.3 Summary of Computational Results

In this section, we brieﬂy discuss sample results for the topology information con-

trol framework applied to self-healing UAV formations dedicated to surveillance

missions. Two double tree networking topologies are represented in Fig. 5.6 as start

conﬁgurations on which the information control and coding schemes previously de-

scribed are applied. Figure 5.7 shows the corresponding converged topologies after

the reconﬁguration process was terminated. In the group communication network-

ing, the decrease of the constraints number and the use of the intrinsic parallelism

Fig. 5.6 UAV formations: start topologies

5 Topology Information Control in Feedback Based Reconﬁguration Processes 121

Fig. 5.7 UAV formations: converged topologies

of the signalling channels, the data control processing is based on coding of coarse-

grain control symbols. Each networking element has a local register ﬁle, ﬁlled from

external caches of control data, global for the whole network. The processing is

applied on larger data sets and the control is distributed. Reconﬁgurable network ar-

chitectures face the problem of keeping under control the communication delays in

reconﬁgurable devices designed in advance technologies. Together with algorithmic

and technological evolutions, reconﬁgurable architectures have to face another chal-

lenge related to their communication energy efﬁciency. Fixed architectures can not

address this kind of energy optimizations when various services or accuracy con-

straints are concerned. Reconﬁgurable architectures can be speciﬁcally conﬁgured

depending on the particular piece of code fragment to be implemented which leads

to interesting group communication behaviors.

The dependency of information control savings on the kth modeling order is

shown in Fig. 5.8. Design ﬂow consists ﬁrst in selecting the applicative domain, and

deﬁning the kind of computations that are typically found into the loop kernels and

122 A. Murgu et al.

Fig. 5.8 Information control savings versus order k

frequently executed code fragments. Creating a bench representative of the targeted

application domain can greatly facilitate the design space exploration by further

reﬁnements of the architecture. Selecting operations at a too low level, such as sum

of absolute differences in image and video processing, or selecting an insufﬁcient

number of functions for the bench will lead to optimize only the peak performance

of the architecture, but this will prove to be not representative enough of a real

applicative behavior, in particular because control statements have a great impact

on the overall performance.

The fundamental objective in topology information control is to maximize the

throughput carried in a networked environment. The closed loop performance was

studied computationally on sample networks that are subject to various trafﬁc ma-

trices. The goal was to assess the performance levels of reconﬁguration processes in

dynamic networking environments.

5.5 Concluding Remarks

In this paper, we have introduced a mathematical framework for information con-

trol and coding occurring in reconﬁguration processes in systems of systems. As

a feedback control mechanism, the iterative parametric dynamic programming is a

good modeling candidate in describing the reconﬁguration computations, where a

multi-objective relational optimization problem is considered in enabling a separa-

tion strategy and ﬁnding the optimal solution in a multilevel fashion. At the lower

5 Topology Information Control in Feedback Based Reconﬁguration Processes 123

processing level, an auxiliary weighted power Lagrangian problem is solved using

dynamic programming associated to the topology control. The iterative paramet-

ric dynamic programming for a class of nonseparable optimization problems ap-

proach extends the reach of dynamic programming and provides an efﬁcient solution

scheme through separation, convexiﬁcation, decomposition, and coordination. The

insights offered by such modeling are useful in deriving resource management pro-

tocols allowing the path selection and QoS parameters monitoring to be taken into

account by the system reconﬁguration mechanism. Distributed topology informa-

tion control among the cooperative network elements regarded as agents broadcast-

ing periodical signals to enable the network connectivity information propagation.

Future work will continue to characterize wireless communication networks and

the information control techniques for guaranteeing the mission performance and

safety of the networked UAVs. In this consideration, communications will be key

and will require further advances based on the results described in this paper. Mul-

tivariable extremum seeking control can be applied to the problem of UAV motion

control in a communication environment, and such approach should lead to im-

provements in the communication ability over position-based policies.

References

1. Elston, J., Frew, E.W., Argrow, B.: Networked UAV communication, command, and control.

In: Proc. AIAA Guidance, Navig., Contr. Conf. (2006)

2. Beard, R., McLain, T., Nelson, D., Kingston, D., Johanson, D.: Decentralized cooperative

aerial surveillance using ﬁxed-wing miniature UAVs. In: Proc. IEEE, vol. 94, no. 7, pp. 1306–

1324 (2006)

3. Rezano, J., Mozos, D., Catthoor, F., Verkest, D.: A reconﬁguration manager for dynamically

reconﬁgurable hardware. In: IEEE Design and Test of Computers, pp. 452–460 (2005)

4. Ross, K.W.: Multiservice Loss Models for Broadband Telecommunication Networks.

Springer, London (1995)

5. Even, S., Tarjan, E.: Network ﬂow and testing graph connectivity. SIAM J. Comput. 4, 507–

518 (1975)

6. IEEE standard for local and metropolitan area networks: virtual bridged local area networks.

IEEE Std 802.1Q-1998

7. IEEE standard for local and metropolitan area networks—common speciﬁcations. Part 3: Me-

dia access control (MAC) bridges—amendment 2: Rapid reconﬁguration amendment to IEEE

Std 802.1D, 1998 Edition. IEEE Std 802.1w-2001

8. Ahlswede, R., Cai, N., Li, S.-Y., Yeung, R.W.: Network information ﬂow. IEEE Trans. Inf.

Theory 46(4), 1204–1216 (2000)

9. Cover, T.M., Thomas, J.: Elements of Information Theory. Wiley, New York (1991)

10. Berger, T.: The Information Theory Approach to Communications. Springer, Berlin (1978)

11. Even, G., Even, S.: Embedding interconnection networks in grid via the layered cross product.

Networks 36(2), 91–95 (2000)

12. Duato, J., Yalamanchili, S., Ni, L.: Interconnection Networks: An Engineering Approach.

IEEE Comput. Soc., Silver Spring (1997)

13. Bertsekas, D.: Nonlinear Programming. Athena Scientiﬁc, Belmont (1995)

14. Fletcher, R.: Practical Method of Optimization. Wiley, New York (1987)

15. Wolinski, C., Kuchcinski, K.: Automatic selection of application-speciﬁc reconﬁgurable pro-

cessor extensions. In: DATE 2008: Proc. of the Conf. on Design, Automation and Test in

Europe, pp. 1214–1219 (2008)

124 A. Murgu et al.

16. Henriksen, S.J.: Estimation of future communications bandwidth requirements for un-

manned aircraft systems operating in the national airspace system. In: Proc. AIAA In-

foTech@Aerospace, vol. 3, pp. 2746–2754 (2007)

17. Dixon, C., Frew, E.W.: Decentralized extremum-seeking control of nonholonomic vehicles to

form a communication chain. In: M.J. Hirsch, P.M. Pardalos, R. Murphey, D. Grundel (eds.),

Advances in Cooperative Control and Optimization. Lecture Notes in Control and Information

Sciences, vol. 369, pp. 311–322 (2007)

18. Vasseur, J.-P., Pickavet, M., Demeester, P.: Network Recovery, Protection and Restoration of

Optical, SONET-SDH, IP, and MPLS. Morgan Kaufman, Amsterdam (2004)

Chapter 6

Effect of Network Geometry and Interference

on Consensus in Wireless Networks

Sundaram Vanka, Vijay Gupta,

and Martin Haenggi

Summary We study the convergence of the average consensus algorithm in wire-

less networks in the presence of interference. It is well known that convergence of

the consensus algorithm improves with network connectivity. However, from a net-

working standpoint, highly connected wireless networks may have lower through-

put because of increased interference. This raises an interesting question: what is

the effect of increased network connectivity on the convergence of the consensus

algorithm, given that this connectivity comes at the cost of lower network through-

put? We address this issue for two types of networks: regular lattices with peri-

odic boundary conditions, and a hierarchical network where a backbone of nodes

arranged as a regular lattice supports a collection of randomly placed nodes. We

characterize the properties of an optimal Time Division Multiple Access (TDMA)

protocol that maximizes the speed of convergence on these networks, and provide

analytical upper and lower bounds for the achievable convergence rate. Our results

show that in an interference-limited scenario the fastest converging interconnection

topology for the consensus algorithm crucially depends on the geometry of node

placement. In particular, we prove that asymptotically in the number of nodes, form-

ing long-range interconnections improves the convergence rate in one-dimensional

tori, while it has the opposite effect in higher dimensions.

6.1 Introduction

Consensus has become an area of increasing research focus in recent years (e.g.,

see [1–8] and the references therein). Given n nodes each with a scalar value and

a possibly time-varying interconnection graph deﬁned on these nodes, a consensus

S. Vanka (



) · V. Gupta · M. Haenggi

Department of Electrical Engineering, University of Notre Dame, Notre Dame, IN 46556, USA

e-mail: svanka@nd.edu

V. Gupta

e-mail: vgupta2@nd.edu

M. Haenggi

e-mail: mhaenggi@nd.edu

M.J. Hirsch et al. (eds.), Dynamics of Information Systems,

Springer Optimization and Its Applications 40, DOI 10.1007/978-1-4419-5689-7_6,

125