Fourier Domain Algorithm for the Fitting Step in Multi-Conjugate Adaptive Optics

Handbook of Constraint Programming495 Francesca Rossi,Peter van Beek,Toby Walshc 2006Elsevier All rights reservedChapter14Finite Domain Constraint Programming SystemsChristian Schulte and Mats CarlssonOne of the main reasons why constraint programming quickly found its way into applica-tions has been the early availability of usable constraint programming systems.Given the wide range of applications using constraint programming it is obvious that one of the key properties of constraint programming systems is their provision of widely reusable services for constructing constraint-based applications.A constraint programming system can be thought of as providing a set of reusable mon services include constraint propagation,search,and services for inter-facing to the system.This chapter looks in more detail at which services are provided by a constraint programming system and in particular what are the key principles and tech-niques in constructing and coordinating these services.To give the chapter a clear focus and a reasonably uniform presentation,we mostly restrict our attention to propagation-basedfinite domain constraint programming systems. That is,systems that solve problems using constraint propagation involving variables rang-ing over somefinite set of integers.The focus onfinite domain constraint programming systems coincides with both practical relevance and known principles and techniques:sys-tems at least offer services forfinite domains;much of the known principles and techniques have been conceived and documented forfinite domains.Essential for a system in providing the services mentioned above are some important abstractions(or objects)to be implemented by a system:variables,implementations for constraints,and so on.Important abstractions for propagation,search,and interfacing are as follows.Constraint propagation.To perform constraint propagation a system needs to imple-ment variables ranging overfinite domains.Constraints expressing a relation among vari-ables are implemented by propagators:software abstractions which by execution perform constraint propagation.Finally,a propagation engine coordinates the execution of propa-gators in order to deliver constraint propagation for a collection of constraints.In Handbook of Constraint Programming,Francesca Rossi,Peter van Beek,Toby Walsh,editors.c 2006 Elsevier,all rights reserved.This copy is for educational and scientific use only.49614.Finite Domain Constraint Programming SystemsSearch.Search in afinite domain constraint programming system has two principal di-mensions.Thefirst dimension is concerned with how to describe the search tree,typically achieved by a branching or labeling.The second dimension is concerned with how to ex-plore a search tree,this is typically achieved by an exploration strategy or search strategy. Any system implementing search must provide a state restoration service which maintains computation states for the nodes of the search tree.Interfacing.A system must provide access to the services mentioned above so that ap-plications can use them.Depending on the underlying constraint programming system, the services can be tightly integrated into some host language(such as Prolog)or being provided by some library(pioneered by ILOG Solver as a C++-based library).Different levels of interfaces can be observed with different systems.Clearly,all sys-tems offer at least interfaces which allow to use the system-provided services in applica-tions.Even though the constraints,search engines,and so on provided by a system are sufficient for many applications,some applications might require more.For these applica-tions,a system must be extensible by new propagators for possibly new constraints,new branching strategies,and new exploration strategies.Chapter structure.The structure of this chapter is as follows.The next section gives a simple architecture forfinite domain constraint programming systems.It describes what a system computes and how computation is organized in principle.The following two Sections14.2and14.3describe how systems implement this architecture.Section14.2de-scribes how propagation is implemented while the following section describes how search is implemented.An overview over existingfinite domain constraint programming systems is provided by Section14.4.The last section of this chapter summarizes the key aspects of afinite domain constraint programming system and presents current and future challenges.14.1Architecture for Constraint Programming SystemsThis section defines a simple architecture of afinite domain constraint programming sys-tem.The section describes what results a system computes and how it computes them.The focus is on the basic entities and principles that are used in systems;the actual implemen-tation techniques used in systems are discussed in the following sections.Much of the content follows the presentation in[58].Essential parts of the architecture described here have beenfirst identified and discussed by Benhamou in[13].14.1.1Propagation-based Constraint SolvingThis section defines terminology and what a system actually computes.Domains.A domain D is a complete mapping from afixed(countable)set of variables V tofinite sets of integers.A domain D is failed,if D(x)=∅for some x∈V.A variable x∈V isfixed by a domain D,if|D(x)|=1.The intersection of domains D1and D2, denoted D1⊓D2,is defined by the domain D(x)=D1(x)∩D2(x)for all x∈V.A domain D1is stronger than a domain D2,written D1⊑D2,if D1(x)⊆D2(x)for all x∈V.Christian Schulte and Mats Carlsson497 We use range notation[l,u]for the set of integers{n∈Z|l≤n≤u}. Assignments and constraints.An integer assignment a is a mapping of variables to integer values,written{x1→n1,...,x k→n k}.We extend the assignment a to map expressions and constraints involving the variables in the natural way.Let vars be the function that returns the set of variables appearing in an assignment.In an abuse of notation,we define an assignment a to be an element of a domain D,written a∈D,if a(x i)∈D(x i)for all x i∈vars(a).The minimum and maximum of an expression e with respect to a domain D are defined as min D e=min{a(e)|a∈D}and max D e=max{a(e)|a∈D}.A constraint c over variables x1,...,x n is a set of assignments a such that vars(a)= {x1,...,x n}.We also define vars(c)={x1,...,x n}.Propagators.A constraint is defined extensionally by a collection of assignments for its variables.Typical systems do not compute with these extensional representations directly for two reasons:1.Representing all possible assignments of a constraint might take too much spaceto be feasible(exponential space in the number of variables).In particular,space becomes an issue if vars(c)contains more than two variables.mon constraints have a certain structure(such as representing a linear equationconstraint or an alldifferent constraint).Representing a constraint extensionally will make it difficult or even impossible to take advantage of this underlying structure.Constraint propagation systems implement a constraint c by a collection of propaga-tors.Propagators are also known asfilters(implemented by somefiltering algorithm)and narrowing operators[13].A propagator p is a function that maps domains to domains. In order to make constraint propagation well-behaved(to be discussed in Section14.1.2), propagators are decreasing and monotonic.•A propagator p must be a decreasing function:p(D)⊑D for all domains D.This property is obvious and guarantees that constraint propagation only removes values.•A propagator p must be a monotonic function:p(D1)⊑p(D2)whenever D1⊑D2.That is,application of p to stronger domains also yields stronger domains.Propagators must faithfully implement constraints.A propagator p is correct for a constraint c iff it does not remove any assignment for c.That is,for all domains D{a∈D}∩c={a∈p(D)}∩cThis is a very weak restriction,for example the identity propagator i with i(D)=D for all domains D is correct for all constraints c.A propagator must also provide sufficient propagation to distinguish solutions from non-solutions.Hence,a set of propagators P is checking for a constraint c,if for domains D where all variables vars(c)arefixed the following holds:p(D)=D for all p∈P, iff the unique assignment a∈D where vars(a)=vars(c)is a solution of c(a∈c).In49814.Finite Domain Constraint Programming Systemsother words,all domains D corresponding to a solution of a constraint c on its variables are required to be afixpoint of the propagator p.A set of propagators P implements a constraint c,if all p∈P are correct for c and P is checking for c.We denote this fact by P=prop(c).Systems consider sets of propagators rather than a single propagator as implementa-tions of constraints to have more freedom in implementing a constraint.For example,a common way to implement simple constraints is by indexicals(to be discussed in Sec-tion14.2.5):a collection of indexical propagators is used to implement a single constraint. On the other hand,systems provide global constraints with the idea that a single propagator implements a constraint involving many variables.Note that only very little propagation is required for a set of propagators to be checking (as the term suggests,checking is sufficient;no actual propagation is required).The level of consistency provided by a propagator set is irrelevant to this model.Consistency levels only provide a convenient way to refer to the strength of propagators.As far as achieving good propagation is concerned,it does not matter whether a propagator set corresponds to a predefined consistency level.What matters is that the propagator set offers a good compromise between strength and cost of propagation.To simplify our presentation we assume that propagators are defined for all variables V. In a system,a propagator p will be only interested in some variables:the variables vars(c) of the constraint c that is implemented by p.Two sets of variables which are important are the input and output variables.The output variables output(p)⊆V of a propagator p are the variables changed by the propagator:x∈output(p)if there exists a domain D such that p(D)(x)=D(x).The input variables input(p)⊆V of a propagator p is the smallest subset V⊆V such that for all domains D1and D2:D1(x)=D2(x)for all x∈V implies that D′1(x)= D′2(x)for all x∈output(p)where D′1=D2⊓p(D1)and D′2=D1⊓p(D2).Only the input variables are useful in computing the application of the propagator to the domain. We say that a propagator p depends on a variable x,if x∈input(p).Example1(Propagators).For the constraint c≡x1≤x2+1the function p1defined by p1(D)(x1)={n∈D(x1)|n≤max D x2+1}and p1(D)(x)=D(x),x=x1is a correct propagator for c.Its output variables are{x1}and its input variables are{x2}.Let D1(x1)={1,5,8}and D1(x2)={1,5},then p1(D1)=D2where D2(x1)=D2(x2)= {1,5}.The propagator p2defined as p2(D)(x2)={n∈D(x2)|n≥min D x1−1}is another correct propagator for c.Here and in the following we assume that a propagator is defined as identity for variables not mentioned in the definition.Its output variables are {x2}and input variables{x1}.The set{p1,p2}is checking for c.For example,the domain D(x1)=D(x2)={2} corresponding to a solution of c is afixpoint of both propagators.The non-solution domain D(x1)={2},D(x2)={0}is not afixpoint(of either propagator).Now we are in the position to describe what a constraint programming system com-putes.A propagation solver for a set of propagators P and some initial domain D, solv(P,D),finds the greatest mutualfixpoint of all the propagators p∈P.In other words, solv(P,D)returns a new domain defined bysolv(P,D)=gfp(λd.iter(P,d))(D)iter(P,D)=⊓p(D)p∈PChristian Schulte and Mats Carlsson499propagate(P f,P n,D)1:N←P n2:P←P f∪P n3:while N=∅do4:p←select(N)5:N←N−{p}6:D′←p(D)7:M←{x∈V|D(x)=D′(x)}8:N←N∪{p′∈P|input(p′)∩M=∅}11:D←D′12:return DFigure14.1:Basic propagation engine propagate.where gfp denotes the greatestfixpoint w.r.t⊑lifted to functions.14.1.2Performing PropagationA constraint programming system is concerned with performing propagation and search. In this section,we consider the propagation engine and postpone the discussion of search to Section14.1.5.The propagation engine propagate shown in Figure14.1computes solv(P,D)for a given set of propagators P and a domain D.Note that lines9and10are left out for an extension to be discussed later.The engine propagate takes two sets of propagators as input where P f contains propagators already known to be atfixpoint for D.This is an im-portant feature to obtain incremental propagation during search.If nofixpoint knowledge on propagators is available,it is safe to execute propagate(∅,P,D).The algorithm uses a set N of propagators to apply(N stands for not known to be atfixpoint).Initially,N contains all propagators from P n.Each time the while loop is executed,a propagator p is deleted from N,p is applied,and the set of modified variables M is computed.All propagators that share input variables with M are added to the set of propagators not known to be atfixpoint.Adding a propagator p to the set N is called scheduling p.An invariant of the engine is that at the while statement p(D)=D for all p∈P−N. The loop terminates,since in each iteration either a propagator is removed from N or a strictly smaller domain D′is computed(as a propagator is a decreasing function and there are onlyfinitely many domains).After termination,the invariant yields that D′= propagate(P f,P n,D)is afixpoint for all p∈P f∪P n,that is propagate(P f,P n,D)= solv(P f∪P n,D).As mentioned,the fact that a propagator is a decreasing function is essential for ter-mination.The fact that a propagator is monotonic guarantees that propagate(P f,P n,D) actually computes solv(P f∪P n,D)and that the order in which propagators are executed does not change the result of propagate(P f,P n,D).The propagation engine(assuming P f=∅)is more or less equivalent to the propagation algorithm of Apt[7,Section7.1.3].50014.Finite Domain Constraint Programming Systems The engine is geared at simplicity,one particular simplification being that it does not pay particular attention to failed domains.That is,even though the domain D becomes failed,propagation continues until a domain is computed that is both failed and afixpoint for all propagators in P.A concrete system might optimize this,as is discussed in Sec-tion14.1.6.Note that propagate leaves undefined how a propagator p is selected from N.Strate-gies for selecting propagators are discussed in Section14.2.1.Example2(Propagation).Consider the propagator p1for the constraint x1≤x2defined byp1(D)(x1)={n∈D(x1)|n≤max D x2}p1(D)(x2)={n∈D(x2)|n≥min D x1}Also consider the propagator p2for the constraint x1≥x2defined analogously.Let us start propagation for the domain D0with D(x1)={0,2,6}and D(x2)= {−1,2,4}by executing propagate(∅,{p1,p2},D0).This initializes both P and N to {p1,p2}.Let us assume that p1is selected for propagation.Then,p1is removed from N and yields D′(x1)={0,2}and D′(x2)={2,4}.The set of modified variables M is{x1,x2} and hence after this iteration N is{p1,p2}.In the second iteration,let us assume that p2is selected for propagation.This yields D′(x1)=D′(x2)={2}.Again,the set of modified variables M is{x1,x2}and hence N is{p1,p2}.Assume that in the next iteration p1is selected.Now D is already afixpoint of p1and the set of modified variables M is empty.This in turn means that N is just{p2}after this iteration.The last iteration selects p2for execution,does not modify the domain,and N becomes empty.Hence,propagate(∅,{p1,p2},D0)returns a domain D with D(x1)=D(x2)= {2}.14.1.3Improving PropagationThe propagation engine shown in Figure14.1is naive in that it does not exploit additional information about propagators.Improved engines being the base for existing systems try to avoid propagator execution based on the knowledge whether a domain is afixpoint for a propagator.In the following we discuss common properties of propagators,which help to avoid useless execution.How a system implements these properties(or detects these properties) is discussed in Section14.2.Idempotent propagators.Assume that a propagator p has actually made the domain stronger,that is,D′=D.This means that there exists a variable x∈V for which D′(x)⊂D(x).Assume further that x∈input(p).Hence p will be included in N.Quite often,however,propagators happen to be idempotent:a propagator p is idempo-tent,if the result of propagation is afixpoint of p.That is,p(p(D))=p(D)for all domains D.Hence,to avoid inclusion of an idempotent propagator p,the following lines can be added to the propagation engine after line8:Christian Schulte and Mats Carlsson501 9:if(p idempotent)then10:N←N−{p}Example3(Idempotent propagators).The propagators p1and p2from Example2are both idempotent as can be seen easily.Taking this into account,propagation takes only three iterations.If the same selection of propagators is done as above,then N is{p2}after thefirst iteration and{p1}after the second iteration.Note that in particular all domain consistent propagators are idempotent. Entailment.An idempotent propagator can be exempted from being included in N di-rectly after p has been applied.A much stronger property for a propagator p is entailment.A propagator p is entailed by a domain D,if all domains D′with D′⊑D arefixpoints of p,that is p(D′)=D′.This means that as soon as a propagator p becomes entailed,it can be safely deleted from the set of propagators P.Example4(Entailed propagator).Consider the propagator p1for the constraint x1≤x2 from Example2.Any domain D with max D x1≤min D x2entails p1.Propagator rewriting.During propagation the domain D mightfix some variables in input(p)∪output(p)of a propagator p.Many propagators can be replaced by simpler propagators after some variables have becomefixed.Example5(Propagator rewriting forfixed variables).Consider the propagator p with p∈prop(c)where c≡x1+x2+x3≤4:p(D)(x1)={n∈D(x1)|n≤max D(4−x2−x3)}Assume that propagation has computed a domain D whichfixes x2to3(that is, D(x2)={3}).Then p can be replaced by the simpler(and most likely more efficient) propagator p′defined by:p′(D)(x1)={n∈D(x1)|n≤max D(1−x3)}A propagator p can always be rewritten to a propagator p′for a domain D,if p(D′)= p′(D′)for all domains D′with D′⊑D.This means that propagator rewriting is not only applicable to domains thatfix variables.This is for example exploited for the“type reduction”of[52]where propagators are rewritten as more knowledge on domains(there called types)becomes available.For ex-ample,the implementation of x0=x1×x2will be replaced by a more efficient one,when all elements in D(x1)and D(x2)are non-negative.14.1.4Propagation EventsFor many propagators it is simple to decide whether they are still at afixpoint for a changed domain based on how the domain has changed.How a domain changes is described by propagation events(or just events).50214.Finite Domain Constraint Programming SystemsExample6(Disequality propagators).Consider the propagator p with{p}=prop(c)for the constraint c≡x1=x2:p(D)(x1)=D(x1)−single(D(x2))p(D)(x2)=D(x2)−single(D(x1))where single(N)for a set N is defined as N if|N|=1and∅otherwise.Clearly,any domain D with|D(x1)|>1and|D(x2)|>1is afixpoint of D.That is, p only needs to be applied if x1or x2arefixed.Similarly,the propagator p1from Example1only needs to be applied to a domain D if max D x2changes and p2from the same example needs to be applied to a domain D if min D x1changes.Assume that the domain D changes to the domain D′⊑D.The usual events defined in a constraint propagation system are:•fix(x):the variable x becomesfixed.•minc(x):the minimum of variable x changes.•maxc(x):the maximum of variable x changes.•any(x):the domain of variable x changes.Clearly the events overlap.Whenever afix(x)event occurs then a minc(x)event,a maxc(x)event,or both events must also occur.If any of thefirst three events occur then an any(x)event occurs.This is captured by the following definition of events(D,D′)for domains D′⊑D:events(D,D′)={any(x)|D′(x)⊂D(X)}∪{minc(x)|min D′x>min D x}∪{maxc(x)|max D′x<max D x}∪{fix(x)||D′(x)|=1and|D(x)|>1} Events satisfy an important monotonicity condition:suppose domains D′′⊑D′⊑D, thenevents(D,D′′)=events(D,D′)∪events(D′,D′′).So an event occurs on a change from D to D′′iff it occurs in the change from D to D′or from D′to D′′.Example7(Events).Let D(x1)={1,2,3},D(x2)={3,4,5,6},D(x3)={0,1}, and D(x4)={7,8,10}while D′(x1)={1,2},D′(x2)={3,5,6}D′(x3)={1}and D′(x4)={7,8,10}.Then events(D,D′)is{maxc(x1),any(x1),any(x2),fix(x3),minc(x3),any(x3)} For a propagator p,the set es(p)⊆{fix(x),minc(x),maxc(x),any(x)|x∈V}of events is an event set for p if the following two properties hold:1.For all domains D′and D with D′⊑D and D(x)=D′(x)for all x∈V−input(p):if p(D)=D and p(D′)=D′,then es(p)∩events(D,D′)=∅.Christian Schulte and Mats Carlsson5032.For all domains D with p(D)=p(p(D)):es(p)∩events(D,p(D))=∅.Thefirst clause of the definition captures the following.If the domain D is afixpointand the stronger domain D′(stronger only on the input variables)is not afixpoint for apropagator p,then an event occurring from changing the domain D to D′must be includedin the event set es(p).The second clause refers to the case when a propagator p does notcompute afixpoint(that is,p(d)=p(p(D))).In this case,an event must occur whenthe domain changes from D to p(D).Note that the second clause never applies to anidempotent propagator.An event set plays an analogous role to the set of input variables:if an event from theevent set occurs when going from a domain D to a domain D′,the propagator is no longerguaranteed to be at afixpoint and must be re-applied.Note that the definition of an event set is rather liberal as the definition does not requirethe event set to be the smallest set:any set that guarantees re-application is allowed.Inparticular,for any propagator p the set{any(x)|x∈input(p)}is an event set:thisevent set makes propagation behave as if no events at all are considered.However,animplementation will try to use event sets that are as small as possible.Example8(Event sets).The propagator p1from Example2depends on the event set{minc(x1),maxc(x2)}.The propagator p from Example6depends on the event set {fix(x1),fix(x2)}.Now it is obvious how the propagation engine from Figure14.1can take advantageof events:instead of considering the set of modified variables and the input variables of apropagator for deciding which propagators are to be included into N,consider the eventsand an event set for a propagator.In other words,replace line8by:8:N←N∪{p′∈P|es(p′)∩events(D,D′)=∅}14.1.5Performing SearchA constraint programming system evaluates solv(P,D)during search.We assume an ex-ecution model for solving a constraint problem with a set of constraints C and an initialdomain D0as follows.We execute the procedure search(∅,P,D0)for an initial set of propagators P= c∈C prop(c).This procedure(shown in Figure14.2)serves as an architecture of a constraint programming system.The procedure requires that D be afixpoint for all propagators in P f(f forfixpoint).The propagators included in P n do not have this requirement(n for not atfixpoint).Thispartitioning of propagators is used for incremental propagation with respect to recursivecalls to search(as discussed below).The somewhat unusual definition of search is quite general.The default branchingstrategy(also known as labeling strategy)for many problems is to choose a variable x suchthat|D(x)|>1and explore x=min D x or x≥min D x+1.This is commonly thought of as changing the domain D for x to either{min D x}or{n∈D(x)|n>min D x}. Branching based on propagator sets for constraints allows for more general strategies,for example x1≤x2or x1>x2.50414.Finite Domain Constraint Programming Systemssearch(P f,P n,D)1:D←propagate(P f,P n,D)2:if D is failed domain then3:return false4:if∃x∈V.|D(x)|>1then5:choose{c1,...,c m}where C∧D|=c1∨···∨c m6:for all i∈[1,m]do7:if search(P f∪P o,prop(c i),D)then8:return true9:return false10:return trueFigure14.2:Architecture of constraint programming system.Note that search has two dimensions:one describes how the search tree looks and the other describes how the search tree is explored.In the above architecture the selection of the c i together with the selection of propagators prop(c i)for the c i describes the shape of the search tree.The sets prop(c i)we refer to as alternatives and the collection of all alternatives is called choice pletely orthogonal is how the search tree is explored.Here,the architecturefixes exploration to be depth-first.Exploration is discussed in more detail in14.3.Note that search performs incremental propagation in the following sense:when call-ing propagate only the propagators prop(c i)for the alternatives are not known to be at a fixpoint.14.1.6Implementing the ArchitectureThis section discusses general approaches to implementing the architecture for a constraint programming system introduced above.The focus is on what needs to be implemented and how the architecture(as an abstraction of a system)relates to a real system.Detecting failure and entailment.In our architecture,failure is only detected inside search after returning from propagate by testing whether the domain obtained by prop-agation is failed.It is clear that a system should optimize detecting failure such that no propagation is wasted if a domain becomes failed and that no inspection of a domain is required to detect failure.A typical way to make the detection of failure or entailment of a propagator more efficient is to let the propagator not only return a domain but also some status information describing whether propagation has resulted in a failed domain or whether the propagator has become entailed.Implementing domains.The architecture describes that a propagator takes a domain as input and returns a new domain.This is too memory consuming for a real system.Instead, a system maintains a single data structure implementing one domain and propagators up-date this single domain when being applied.Inspecting propagate in Figure14.1it becomes clear that maintaining a single domain is straightforward to achieve.The only reason for having a domain D and D′is in order to be able to identify the modified variables M.State restoration.For propagation,systems maintain a single domain as has been argued above.However,a single domain becomes an issues for search:when calling search re-cursively as in Figure14.2and a domain is not transferred as a copy,backtracking(that is, returning from the recursive call)needs to restore the domain.State restoration is not limited to domains but also includes private states of propagators and also whether propagators have become entailed.State restoration is a key service required in a constraint programming system and is discussed in Section14.3.2in detail.Finding dependent propagators.After applying a propagator,propagate must com-pute the events(similar to the set of modified variables)in order tofind all propagators that depend on these events.Clearly,this requires that a system be able to compute the events andfind the dependent propagators efficiently.Variables for propagators.In addition to the fact that propagators update a single do-mains rather than returning domains,implementations need to be careful in how many variables are referenced by a propagator.In our architecture,propagators are defined for all variables in V.However,from the above discussion it is clear that a propagator p is only concerned with variables input(p)∪output(p).Quite often,the variables in input(p)∪output(p)are called the parameters of p.A system will implement a propagator p such that it maintains its input(p)∪output(p) in some datastructure,typically as an array or list of variables.While most of the properties discussed for our architecture readily carry over to this extended setup,the case of multiple occurrences of the same variable in the datastructure maintained by a propagator needs special attention.Multiple variable occurrences and unification.Depending on the actual system,mul-tiple occurrences may both be common and appear dynamically.Here,dynamic means that variable occurrences for a propagator p might become the same during some computation not performed by p itself.This is typically the case when the constraint programming sys-tem is embedded in a constraint logic programming host language featuring unification for logical variables.Unification makes two variables x and y equal without the requirement to assign the variables a particular value.In this case the variables x and y are also said to be aliased.The main issues with multiple occurrences of the same variable are that they make(a) detection of idempotence and(b)achieving good propagation more difficult,as is discussed in Section14.2.3.Private state.In our architecture,propagators are functions.In systems,propagators often need to maintain some private state.Private state is for example used to achieve incrementality,more information is given in Section14.2.3.。

费希尔算法The Fischer algorithm is a renowned technique in the field of cryptography, specifically designed to address the challenges associated with secure key exchange in a distributed network. Developed by Ralph Merkle and Martin Hellman, this algorithm enables two parties to establish a shared secret key over an insecure communication channel without the need for a prior exchange of secret information.费希尔算法是密码学领域中的一项著名技术，专门用于解决分布式网络中安全密钥交换的挑战。

该算法由拉尔夫·默克尔（Ralph Merkle）和马丁·赫尔曼（Martin Hellman）开发，它允许两个参与方在不安全的通信通道上建立共享的秘密密钥，而无需事先交换秘密信息。

At the core of the Fischer algorithm lies the concept of public-key cryptography. Each party possesses a pair of keys: a public key, which can be freely shared, and a private key, kept securely. The algorithm ensures that messages encrypted with one key can only be decrypted with the other, and vice versa. This asymmetric nature is crucial for establishing secure communication.费希尔算法的核心在于公钥密码学的概念。

普林斯顿算法
普林斯顿算法是一种用于解决最短路径问题的一种经典算法，也称为迪杰斯特拉算法。

它是一种贪婪算法，逐步构建最短路径树，从起始节点开始，依次选择与当前节点距离最近的节点，并更新该节点到其他节点的距离。

通过不断选择最短路径上的节点，最终得到起点到各个节点的最短路径。

普林斯顿算法的基本步骤如下：
1. 创建一个距离列表distances，用于保存起始节点到各个节点的最短距离，初始值为无穷大（表示未知路径）。

2. 创建一个前驱列表predecessors，用于保存路径上每个节点
的前驱节点，初始值为None。

3. 将起始节点的距离设置为0，即distances[start_node] = 0。

4. 选择距离最短且未被访问的节点作为当前节点。

5. 更新当前节点到邻居节点的距离，如果新的距离比原来的距离小，则更新距离和前驱节点。

6. 标记当前节点为已访问。

7. 重复步骤4-6直到所有节点都被访问。

8. 根据distances和predecessors构建最短路径。

普林斯顿算法的时间复杂度为O(V^2)，其中V为节点数。

它
适用于处理节点数不太大的图，但在节点数非常大时，性能可能较差。

为了提高效率，还有一种优化的算法称为堆优化的迪杰斯特拉算法，它使用优先队列来选择最短距离的节点，使得时间复杂度降为O((V+E)logV)，其中E为边数。

LEOPOLD-FRANZENS UNIVERSITYChair of Engineering Mechanicso.Univ.-Prof.Dr.-Ing.habil.G.I.Schu¨e ller,Ph.D.G.I.Schueller@uibk.ac.at Technikerstrasse13,A-6020Innsbruck,Austria,EU Tel.:+435125076841Fax.:+435125072905 mechanik@uibk.ac.at,http://mechanik.uibk.ac.atIfM-Publication2-407G.I.Schu¨e ller.Developments in stochastic structural mechanics.Archive of Applied Mechanics,published online,2006.Archive of Applied Mechanics manuscript No.(will be inserted by the editor)Developments in Stochastic Structural MechanicsG.I.Schu¨e llerInstitute of Engineering Mechanics,Leopold-Franzens University,Innsbruck,Aus-tria,EUReceived:date/Revised version:dateAbstract Uncertainties are a central element in structural analysis and design.But even today they are frequently dealt with in an intuitive or qualitative way only.However,as already suggested80years ago,these uncertainties may be quantified by statistical and stochastic procedures. In this contribution it is attempted to shed light on some of the recent advances in the now establishedfield of stochastic structural mechanics and also solicit ideas on possible future developments.1IntroductionThe realistic modeling of structures and the expected loading conditions as well as the mechanisms of their possible deterioration with time are un-doubtedly one of the major goals of structural and engineering mechanics2G.I.Schu¨e ller respectively.It has been recognized that this should also include the quan-titative consideration of the statistical uncertainties of the models and the parameters involved[56].There is also a general agreement that probabilis-tic methods should be strongly rooted in the basic theories of structural en-gineering and engineering mechanics and hence represent the natural next step in the development of thesefields.It is well known that modern methods leading to a quantification of un-certainties of stochastic systems require computational procedures.The de-velopment of these procedures goes in line with the computational methods in current traditional(deterministic)analysis for the solution of problems required by the engineering practice,where certainly computational pro-cedures dominate.Hence,their further development within computational stochastic structural analysis is a most important requirement for dissemi-nation of stochastic concepts into engineering practice.Most naturally,pro-cedures to deal with stochastic systems are computationally considerably more involved than their deterministic counterparts,because the parameter set assumes a(finite or infinite)number of values in contrast to a single point in the parameter space.Hence,in order to be competitive and tractable in practical applications,the computational efficiency of procedures utilized is a crucial issue.Its significance should not be underestimated.Improvements on efficiency can be attributed to two main factors,i.e.by improved hard-ware in terms of ever faster computers and improved software,which means to improve the efficiency of computational algorithms,which also includesDevelopments in Stochastic Structural Mechanics3 utilizing parallel processing and computer farming respectively.For a con-tinuous increase of their efficiency by software developments,computational procedure of stochastic analysis should follow a similar way as it was gone in the seventieth and eighties developing the deterministic FE approach. One important aspect in this fast development was the focus on numerical methods adjusted to the strength and weakness of numerical computational algorithms.In other words,traditional ways of structural analysis devel-oped before the computer age have been dropped,redesigned and adjusted respectively to meet the new requirements posed by the computational fa-cilities.Two main streams of computational procedures in Stochastic Structural Analysis can be observed.Thefirst of this main class is the generation of sample functions by Monte Carlo simulation(MCS).These procedures might be categorized further according to their purpose:–Realizations of prescribed statistical information:samples must be com-patible with prescribed stochastic information such as spectral density, correlation,distribution,etc.,applications are:(1)Unconditional simula-tion of stochastic processes,fields and waves.(2)Conditional simulation compatible with observations and a priori statistical information.–Assessment of the stochastic response for a mathematical model with prescribed statistics(random loading/system parameters)of the param-eters,applications are:(1)Representative sample for the estimation of the overall distribution.4G.I.Schu¨e ller Indiscriminate(blind)generation of samples.Numerical integration of SDE’s.(2)Representative sample for the reliability assessment by gen-erating adverse rare events with positive probability,i.e.by:(a)variance reduction techniques controlling the realizations of RV’s,(b)controlling the evolution in time of sampling functions.The other main class provides numerical solutions to analytical proce-dures.Grouping again according to the respective purpose the following classification can be made:Numerical solutions of Kolmogorov equations(Galerkin’s method,Finite El-ement method,Path Integral method),Moment Closure Schemes,Compu-tation of the Evolution of Moments,Maximum Entropy Procedures,Asymp-totic Stability of Diffusion Processes.In the following,some of the outlined topics will be addressed stressing new developments.These topics are described within the next six subject areas,each focusing on a different issue,i.e.representation of stochastic processes andfields,structural response,stochastic FE methods and parallel processing,structural reliability and optimization,and stochastic dynamics. In this context it should be mentioned that aside from the MIT-Conference series the USNCCM,ECCM and WCCM’s do have a larger part of sessions addressing computational stochastic issues.Developments in Stochastic Structural Mechanics5 2Representation of Stochastic ProcessesMany quantities involving randomfluctuations in time and space might be adequately described by stochastic processes,fields and waves.Typical ex-amples of engineering interest are earthquake ground motion,sea waves, wind turbulence,road roughness,imperfection of shells,fluctuating prop-erties in random media,etc.For this setup,probabilistic characteristics of the process are known from various measurements and investigations in the past.In structural engineering,the available probabilistic characteristics of random quantities affecting the loading or the mechanical system can be often not utilized directly to account for the randomness of the structural response due to its complexity.For example,in the common case of strong earthquake motion,the structural response will be in general non-linear and it might be too difficult to compute the probabilistic characteristics of the response by other means than Monte Carlo simulation.For the purpose of Monte Carlo simulation sample functions of the involved stochastic pro-cess must be generated.These sample functions should represent accurately the characteristics of the underlying stochastic process orfields and might be stationary and non-stationary,homogeneous or non-homogeneous,one-dimensional or multi-dimensional,uni-variate or multi-variate,Gaussian or non-Gaussian,depending very much on the requirements of accuracy of re-alistic representation of the physical behavior and on the available statistical data.6G.I.Schu¨e ller The main requirement on the sample function is its accurate represen-tation of the available stochastic information of the process.The associ-ated mathematical model can be selected in any convenient manner as long it reproduces the required stochastic properties.Therefore,quite different representations have been developed and might be utilized for this purpose. The most common representations are e.g.:ARMA and AR models,Filtered White Noise(SDE),Shot Noise and Filtered Poisson White Noise,Covari-ance Decomposition,Karhunen-Lo`e ve and Polynomial Chaos Expansion, Spectral Representation,Wavelets Representation.Among the various methods listed above,the spectral representation methods appear to be most widely used(see e.g.[71,86]).According to this procedure,samples with specified power spectral density information are generated.For the stationary or homogeneous case the Fast Fourier Transform(FFT)techniques is utilized for a dramatic improvements of its computational efficiency(see e.g.[104,105]).Advances in thisfield provide efficient procedures for the generation of2D and3D homogeneous Gaus-sian stochasticfields using the FFT technique(see e.g.[87]).The spectral representation method generates ergodic sample functions of which each ful-fills exactly the requirements of a target power spectrum.These procedures can be extended to the non-stationary case,to the generation of stochastic waves and to incorporate non-Gaussian stochasticfields by a memoryless nonlinear transformation together with an iterative procedure to meet the target spectral density.Developments in Stochastic Structural Mechanics7 The above spectral representation procedures for an unconditional simula-tion of stochastic processes andfields can also be extended for Conditional simulations techniques for Gaussianfields(see e.g.[43,44])employing the conditional probability density method.The aim of this procedure is the generation of Gaussian random variates U n under the condition that(n−1) realizations u i of U i,i=1,2,...,(n−1)are specified and the a priori known covariances are satisfied.An alternative procedure is based on the so called Kriging method used in geostatistical application and applied also to con-ditional simulation problems in earthquake engineering(see e.g.[98]).The Kriging method has been improved significantly(see e.g.[36])that has made this method theoretically clearer and computationally more efficient.The differences and similarities of the conditional probability density methods and(modified)Kriging methods are discussed in[37]showing the equiva-lence of both procedures if the process is Gaussian with zero mean.A quite general spectral representation utilized for Gaussian random pro-cesses andfields is the Karhunen-Lo`e ve expansion of the covariance function (see e.g.[54,33]).This representation is applicable for stationary(homoge-neous)as well as for non-stationary(inhomogeneous)stochastic processes (fields).The expansion of a stochastic process(field)u(x,θ)takes the formu(x,θ)=¯u(x)+∞i=1ξ(θ) λiφi(x)(1)where the symbolθindicates the random nature of the corresponding quan-tity and where¯u(x)denotes the mean,φi(x)are the eigenfunctions andλi the eigenvalues of the covariance function.The set{ξi(θ)}forms a set of8G.I.Schu¨e ller orthogonal(uncorrelated)zero mean random variables with unit variance.The Karhunen-Lo`e ve expansion is mean square convergent irrespective of its probabilistic nature provided it possesses afinite variance.For the im-portant special case of a Gaussian process orfield the random variables{ξi(θ)}are independent standard normal random variables.In many prac-tical applications where the random quantities vary smoothly with respectto time or space,only few terms are necessary to capture the major part of the randomfluctuation of the process.Its major advantage is the reduction from a large number of correlated random variables to few most important uncorrelated ones.Hence this representation is especially suitable for band limited colored excitation and stochastic FE representation of random me-dia where random variables are usually strongly correlated.It might also be utilized to represent the correlated stochastic response of MDOF-systems by few most important variables and hence achieving a space reduction.A generalization of the above Karhunen-Lo`e ve expansion has been proposed for application where the covariance function is not known a priori(see[16, 33,32]).The stochastic process(field)u(x,θ)takes the formu(x,θ)=a0(x)Γ0+∞i1=1a i1(x)Γ1(ξi1(θ))+∞i1=1i1i2=1a i1i2(x)Γ2(ξi1(θ),ξi2(θ))+ (2)which is denoted as the Polynomial Chaos Expansion.Introducing a one-to-one mapping to a set with ordered indices{Ψi(θ)}and truncating eqn.2Developments in Stochastic Structural Mechanics9 after the p th term,the above representations reads,u(x,θ)=pj=ou j(x)Ψj(θ)(3)where the symbolΓn(ξi1,...,ξin)denotes the Polynomial Chaos of order nin the independent standard normal random variables.These polynomialsare orthogonal so that the expectation(or inner product)<ΨiΨj>=δij beingδij the Kronecker symbol.For the special case of a Gaussian random process the above representation coincides with the Karhunen-Lo`e ve expan-sion.The Polynomial Chaos expansion is adjustable in two ways:Increasingthe number of random variables{ξi}results in a refinement of the random fluctuations,while an increase of the maximum order of the polynomialcaptures non-linear(non-Gaussian)behavior of the process.However,the relation between accuracy and numerical efforts,still remains to be shown. The spectral representation by Fourier analysis is not well suited to describe local feature in the time or space domain.This disadvantage is overcome in wavelets analysis which provides an alternative of breaking a signal down into its constituent parts.For more details on this approach,it is referred to[24,60].In some cases of applications the physics or data might be inconsistent with the Gaussian distribution.For such cases,non-Gaussian models have been developed employing various concepts to meet the desired target dis-tribution as well as the target correlation structure(spectral density).Cer-tainly the most straight forward procedures is the above mentioned memo-ryless non-linear transformation of Gaussian processes utilizing the spectralrepresentation.An alternative approach utilizes linear and non-linearfil-ters to represent normal and non-Gaussian processes andfields excited by Gaussian white noise.Linearfilters excited by polynomial forms of Poisson white noise have been developed in[59]and[34].These procedures allow the evaluation of moments of arbitrary order without having to resort to closure techniques. Non-linearfilters are utilized to generate a stationary non-Gaussian stochas-tic process in agreement with a givenfirst-order probability density function and the spectral density[48,15].In the Kontorovich-Lyandres procedure as used in[48],the drift and diffusion coefficients are selected such that the solutionfits the target probability density,and the parameters in the solu-tion form are then adjusted to approximate the target spectral density.The approach by Cai and Lin[15]simplifies this procedure by matching the spec-tral density by adjusting only the drift coefficients,which is the followed by adjusting the diffusion coefficient to approximate the distribution of the pro-cess.The latter approach is especially suitable and computationally highly efficient for a long term simulation of stationary stochastic processes since the computational expense increases only linearly with the number n of dis-crete sample points while the spectral approach has a growth rate of n ln n when applying the efficient FFT technique.For generating samples of the non-linearfilter represented by a stochastic differential equations(SDE), well developed numerical procedures are available(see e.g.[47]).3Response of Stochastic SystemsThe assessment of the stochastic response is the main theme in stochastic mechanics.Contrary to the representation of of stochastic processes and fields designed tofit available statistical data and information,the output of the mathematical model is not prescribed and needs to be determined in some stochastic sense.Hence the mathematical model can not be selected freely but is specified a priori.The model involves for stochastic systems ei-ther random system parameters or/and random loading.Please note,due to space limitations,the question of model validation cannot be treated here. For the characterization of available numerical procedures some classifi-cations with regard to the structural model,loading and the description of the stochastic response is most instrumental.Concerning the structural model,a distinction between the properties,i.e.whether it is determinis-tic or stochastic,linear or non-linear,as well as the number of degrees of freedom(DOF)involved,is essential.As a criterion for the feasibility of a particular numerical procedure,the number of DOF’s of the structural system is one of the most crucial parameters.Therefore,a distinction be-tween dynamical-system-models and general FE-discretizations is suggested where dynamical systems are associated with a low state space dimension of the structural model.FE-discretization has no essential restriction re-garding its number of DOF’s.The stochastic loading can be grouped into static and dynamic loading.Stochastic dynamic loading might be charac-terized further by its distribution and correlation and its independence ordependence on the response,resulting in categorization such as Gaussian and non-Gaussian,stationary and non-stationary,white noise or colored, additive and multiplicative(parametric)excitation properties.Apart from the mathematical model,the required terms in which the stochastic re-sponse should be evaluated play an essential role ranging from assessing thefirst two moments of the response to reliability assessments and stabil-ity analysis.The large number of possibilities for evaluating the stochas-tic response as outlined above does not allow for a discussion of the en-tire subject.Therefore only some selected advances and new directions will be addressed.As already mentioned above,one could distinguish between two main categories of computational procedures treating the response of stochastic systems.Thefirst is based on Monte Carlo simulation and the second provides numerical solutions of analytical procedures for obtaining quantitative results.Regarding the numerical solutions of analytical proce-dures,a clear distinction between dynamical-system-models and FE-models should be made.Current research efforts in stochastic dynamics focus to a large extent on dynamical-system-models while there are few new numerical approaches concerning the evaluation of the stochastic dynamic response of e.g.FE-models.Numerical solutions of the Kolmogorov equations are typical examples of belonging to dynamical-system-models where available approaches are computationally feasible only for state space dimensions one to three and in exceptional cases for dimension four.Galerkin’s,Finite El-ement(FE)and Path Integral methods respectively are generally used tosolve numerically the forward(Fokker-Planck)and backward Kolmogorov equations.For example,in[8,92]the FE approach is employed for stationary and transient solutions respectively of the mentioned forward and backward equations for second order systems.First passage probabilities have been ob-tained employing a Petrov-Galerkin FE method to solve the backward and the related Pontryagin-Vitt equations.An instructive comparison between the computational efforts using Monte Carlo simulation and the FE-method is given e.g.in an earlier IASSAR report[85].The Path Integral method follows the evolution of the(transition)prob-ability function over short time intervals,exploiting the fact that short time transition probabilities for normal white noise excitations are locally Gaus-sian distributed.All existing path integration procedures utilize certain in-terpolation schemes where the probability density function(PDF)is rep-resented by values at discrete grid points.In a wider sense,cell mapping methods(see e.g.[38,39])can be regarded as special setups of the path integral procedure.As documented in[9],cumulant neglect closure described in section7.3 has been automated putational procedures for the automated generation and solutions of the closed set of moment equations have been developed.The method can be employed for an arbitrary number of states and closed at arbitrary levels.The approach,however,is limited by available computational resources,since the computational cost grows exponentially with respect to the number of states and the selected closurelevel.The above discussed developments of numerical procedures deal with low dimensional dynamical systems which are employed for investigating strong non-linear behavior subjected to(Gaussian)white noise excitation. Although dynamical system formulations are quite general and extendible to treat non-Gaussian and colored(filtered)excitation of larger systems,the computational expense is growing exponentially rendering most numerical approaches unfeasible for larger systems.This so called”curse of dimen-sionality”is not overcome yet and it is questionable whether it ever will be, despite the fast developing computational possibilities.For this reason,the alternative approach based on Monte Carlo simu-lation(MCS)gains importance.Several aspects favor procedures based on MCS in engineering applications:(1)Considerably smaller growth rate of the computational effort with dimensionality than analytical procedures.(2) Generally applicable,well suited for parallel processing(see section5.1)and computationally straight forward.(3)Non-linear complex behavior does not complicate the basic procedure.(4)Manageable for complex systems.Contrary to numerical solutions of analytical procedures,the employed structural model and the type of stochastic loading does for MCS not play a deceive role.For this reason,MCS procedures might be structured ac-cording to their purpose i.e.where sample functions are generated either for the estimation of the overall distribution or for generating rare adverse events for an efficient reliability assessment.In the former case,the prob-ability space is covered uniformly by an indiscriminate(blind)generationof sample functions representing the random quantities.Basically,at set of random variables will be generated by a pseudo random number generator followed by a deterministic structural analysis.Based on generated random numbers realizations of random processes,fields and waves addressed in section2,are constructed and utilized without any further modification in the following structural analysis.The situation may not be considered to be straight forward,however,in case of a discriminate MCS for the reliability estimation of structures,where rare events contributing considerably to the failure probability should be gener-ated.Since the effectiveness of direct indiscriminate MCS is not satisfactory for producing a statistically relevant number of low probability realizations in the failure domain,the generation of samples is restricted or guided in some way.The most important class are the variance reduction techniques which operate on the probability of realizations of random variables.The most widely used representative of this class in structural reliability assess-ment is Importance Sampling where a suitable sampling distribution con-trols the generation of realizations in the probability space.The challenge in Importance Sampling is the construction of a suitable sampling distribu-tion which depends in general on the specific structural system and on the failure domain(see e.g.[84]).Hence,the generation of sample functions is no longer independent from the structural system and failure criterion as for indiscriminate direct MCS.Due to these dependencies,computational procedures for an automated establishment of sampling distributions areurgently needed.Adaptive numerical strategies utilizing Importance Direc-tional sampling(e.g.[11])are steps in this direction.The effectiveness of the Importance sampling approach depends crucially on the complexity of the system response as well as an the number of random variables(see also section5.2).Static problems(linear and nonlinear)with few random vari-ables might be treated effectively by this approach.Linear systems where the randomness is represented by a large number of RVs can also be treated efficiently employingfirst order reliability methods(see e.g.[27]).This ap-proach,however,is questionable for the case of non-linear stochastic dynam-ics involving a large set of random variables,where the computational effort required for establishing a suitable sampling distribution might exceed the effort needed for indiscriminate direct MCS.Instead of controlling the realization of random variables,alternatively the evolution of the generated sampling can be controlled[68].This ap-proach is limited to stochastic processes andfields with Markovian prop-erties and utilizes an evolutionary programming technique for the genera-tion of more”important”realization in the low probability domain.This approach is especially suitable for white noise excitation and non-linear systems where Importance sampling is rather difficult to apply.Although the approach cannot deal with spectral representations of the stochastic processes,it is capable to make use of linearly and non-linearlyfiltered ex-citation.Again,this is just contrary to Importance sampling which can be applied to spectral representations but not to white noisefiltered excitation.4Stochastic Finite ElementsAs its name suggests,Stochastic Finite Elements are structural models rep-resented by Finite Elements the properties of which involve randomness.In static analysis,the stiffness matrix might be random due to unpredictable variation of some material properties,random coupling strength between structural components,uncertain boundary conditions,etc.For buckling analysis,shape imperfections of the structures have an additional impor-tant effect on the buckling load[76].Considering structural dynamics,in addition to the stiffness matrix,the damping properties and sometimes also the mass matrix might not be predictable with certainty.Discussing numerical Stochastic Finite Elements procedures,two cat-egories should be distinguished clearly.Thefirst is the representation of Stochastic Finite Elements and their global assemblage as random structural matrices.The second category addresses the evaluation of the stochastic re-sponse of the FE-model due to its randomness.Focusingfirst on the Stochastic FE representation,several representa-tions such as the midpoint method[35],the interpolation method[53],the local average method[97],as well as the Weighted-Integral-Method[94,25, 26]have been developed to describe spatial randomfluctuations within the element.As a tendency,the midpoint methods leads to an overestimation of the variance of the response,the local average method to an underestima-tion and the Weighted-Integral-Method leads to the most accurate results. Moreover,the so called mesh-size problem can be resolved utilizing thisrepresentation.After assembling all Finite Elements,the random structural stiffness matrix K,taken as representative example,assumes the form,K(α)=¯K+ni=1K Iiαi+ni=1nj=1K IIijαiαj+ (4)where¯K is the mean of the matrix,K I i and K II ij denote the determinis-ticfirst and second rate of change with respect to the zero mean random variablesαi andαj and n is the total number of random variables.For normally distributed sets of random variables{α},the correlated set can be represented advantageously by the Karhunen-Lo`e ve expansion[33]and for non-Gaussian distributed random variables by its Polynomial chaos ex-pansion[32],K(θ)=¯K+Mi=0ˆKiΨi(θ)(5)where M denotes the total number of chaos polynomials,ˆK i the associated deterministicfluctuation of the matrix andΨi(θ)a polynomial of standard normal random variablesξj(θ)whereθindicates the random nature of the associated variable.In a second step,the random response of the stochastic structural system is determined.The most widely used procedure for evaluating the stochastic response is the well established perturbation approach(see e.g.[53]).It is well adapted to the FE-formulation and capable to evaluatefirst and second moment properties of the response in an efficient manner.The approach, however,is justified only for small deviations from the center value.Since this assumption is satisfied in most practical applications,the obtainedfirst two moment properties are evaluated satisfactorily.However,the tails of the。

菲茨定律与互联网设计（Fitts’ Law）菲茨定律是用来预测从任意一点到目标中心位置所需时间的数学模型。

它由保罗.菲茨在1954年首先提出。

这个模型考虑了用户定位点的初始位置与目标的相对距离以及目标的大小。

菲茨定律虽然在很多领域都得到了应用但其在人机交互（HCI）和设计领域的影响却最为广泛和深远。

（用于估算用户移动光标点击链接或控件按钮所需的时间）目的地明确的移动可以细分为两个部分：首先一个大幅度的移动将光标移向与目标大致相同的方向和区域；紧接着是一系列精细的小幅度微调来将光标精确定位在目标中心。

你现在就可以做一个小实验来观察这一过程–举起你的手臂并试着用手指指向远处的一个小物体，例如远处墙上的一个电灯开关。

开始你的手臂可能会往开关的位置大幅的移动而且很有可能稍微过头了一点。

接下来你会做一些微小的调整动作直至你的手指正好对准目标开关的中心。

现在你可以试着指向一个更大的物体–比如说电视或一面墙壁。

这一次你也会以大幅度的手臂动作来使手指指向目标方向，但因为目标体积很大所以一般情况下你只需要做很少（甚至不需要任何)的微调。

让我们来看下面这个例子。

图中的红色盒子代表目标；虚线代表从起点至目标的移动轨迹，目标上灰色左右箭头之间的范围是用户光标减速并微调以弥补误差的区域。

在右方有一个较大的目标，因为面积很大所以用户从任意点快速点击应该不会很难：大的目标区域意味着光标在目标上停下来之前不需要做太精细的调整在下一个例子中，屏幕的右方有一个小得多的目标所以用户快速点击目标会困难得多。

因为用户需要将光标移动较长距离而且目标面积很小所以在光标正确的对准目标前需要做一系列精细的调整动作。

但如果同样大小的目标距离很近的话，因为到达目标范围所需的初始动作很小所以准确点击它的难度也会小很多。

距离越近，初始动作因为幅度太大而超出目标区域的风险就越小。

对于形状不规则的目标而言，目标区域的大小和移动的方向是相对的。

在下面的例子中，如果用户从和目标平行的位置水平移动光标，那么这个按钮的相对目标区域就很大。

等价多路径间流量分配调度算法研究1 233林伟，刘斌，唐毅（1．清华大学深圳研究生院广东深圳 518055；2. 香港城市大学香港；3．清华大学计算机科学与技术系，北京 100084）lin-w04@摘要：为了减少网络拥塞并充分利用链路带宽，当在转发节点与目的子网间存在有多条等价路径（ECMPs）时，流量负载应该在ECMPs间均衡分配，并且属于同一个TCP流的IP分组应该按照相同顺序到达目的主机。

本文提出了一种基于LRU1 Cache和计数统计的算法。

该算法通过为每条ECMP分配一个计数器，利用计数统计从而考虑到了IP分组的长度差异。

使用相对计数以及对某些情况增加约束条件解决了计数器溢出问题。

UDP分组只需要作为调节负载均衡的流量。

更进一步，对于去往同一目的子网的不同主机的TCP流的时延差异被转化为cache中的表项失效的时间长度差。

仿真实验表明，当ECMPs间的时延差不显著的情况下，只需要很小的存储空间，且每次cache查找只需要一个时钟周期，负载均衡接近最优，此时只有2%的分组出现乱序。

关键词：流量分配；等价多路径；LRU；Cache；计数统计中图分类号：TP393.051 引言随着Internet网络规模的的迅速扩大，其拓扑结构日趋复杂。

从流量工程、可靠性和网络安全等因素考虑，网络中的两个节点间部署了多条路径。

目前，绝大部分单一路径路由协议都是基于dijkstra的最短路径算法，只有开销最小的路径被选为路由路径。

按照这种算法，网络所提供的带宽没有被充分利用，有可能出现多条路径中的一条路径负载过重，而其他路径却处于空闲状态，如此将造成网络的局部拥塞。

当IP分组经过多个节点之后，负载不均衡的情况可能会进一步加剧。

如果存在多于一条的路径的开销近似相等，单一路径路由协议的计算结果会在这几条路径间变化，造成频繁的路由表更新，网络变得不稳定，性能也受到影响[1]。

与单一路径路由协议不同，等价多路径路由协议被提出用以解决上述的问题[2, 3]。

The Flooding Time Synchronization ProtocolMiklós Maróti Branislav Kusy Gyula Simon Ákos LédecziInstitute for Software Integrated SystemsVanderbilt University2015 Terrace Place, Nashville, TN 37203, USAPhone: (+1) 615-343-7472e-mail: {miklos.maroti, branislav.kusy, gyula.simon, akos.ledeczi}@ABSTRACTWireless sensor network applications, similarly to other distributed systems, often require a scalable time synchronization service enabling data consistency and coordination. This paper describes the Flooding Time Synchronization Protocol (FTSP), especially tailored for applications requiring stringent precision on resource limited wireless platforms. The proposed time synchronization protocol uses low communication bandwidth and it is robust against node and link failures. The FTSP achieves its robustness by utilizing periodic flooding of synchronization messages, and implicit dynamic topology update. The unique high precision performance is reached by utilizing MAC-layer time-stamping and comprehensive error compensation including clock skew estimation. The sources of delays and uncertainties in message transmission are analyzed in detail and techniques are presented to mitigate their effects. The FTSP was implemented on the Berkeley Mica2 platform and evaluated in a 60-node, multi-hop setup. The average per-hop synchronization error was in the one microsecond range, which is markedly better than that of the existing RBS and TPSN algorithms.Categories and Subject DescriptorsC.2 [COMPUTER-COMMUNICATION NETWORKS]: Network Architecture and Design, Network Protocols.General TermsAlgorithms, Design, Performance, Reliability, Experimentation. KeywordsSensor Networks, Time Synchronization, Clock Synchronization, Clock Drift, Multi-hop.1.INTRODUCTIONThe advances in micro electro-mechanical systems (MEMS) technology, in digital circuits design, integration and packaging, and in wireless communication are leading to smaller, cheaper and low-power sensing and computing devices. Cell phones and handheld computers already enjoy the increased popularity of the public. These trends point towards radically new systems of thousands or even millions of tiny computing devices interacting with the environment and communicating with each other. Research teams are working on incorporating sensing, processing and communication in a volume of less than one cubic millimeter [6], while devices of the size of a coin built from off-the-shelf components are commercially available already. The UC Berkeley Mica2 and Mica2Dot motes are popular research platforms of this emerging technology [19].Complex networks built from thousands of such devices are expected to affect many aspects of our lives. The potential applications of wireless sensor networks (WSN) include: •Monitoring applications: Non-intrusive and non-disruptive environmental monitoring helps biologists to study sensitive wildlife habitats and people with certain medical conditions can receive constant monitoring through sensors [12]. Sensor networks monitor the structural health of the Golden Gate Bridge in San Francisco and the microclimates on Great Duck Island, Maine [9].•Mobile commerce, inventory management: by measuring continuously changing conditions, WSN will influence the movement of commodities to locations where the need exists. •Smart office, kindergarten: systems containing wireless sensors will be an integral part of our office space. They would improve the education process by tailoring it to the individual needs of a child [14], adapt to context, and coordinate activities of multiple children.•Military applications: potential applications include surveillance, target tracking [15], countersniper systems [10] or battlefield monitoring that propagates information to the soldiers and vehicles involved in combat.WSN are large-scale distributed systems, yet their unique characteristics, especially the severe resource constraints, require the reevaluation of traditional distributed algorithms for problems once considered to be solved. One of the basic middleware services of sensor networks is time synchronization. Time synchronization is required for consistent distributed sensing and control. Furthermore, common services in WSN, such as coordination, communication, security, power management or distributed logging also depend on the existence of global time.In this paper, we describe the Flooding Time Synchronization Protocol (FTSP) for WSN in detail. When designing the FTSP, our goals were to achieve network-wide time synchronization with error in the micro-second range and scalability up toPermission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.SenSys’04, November 3–5, 2004, Baltimore, Maryland, USA. Copyright 2004 ACM 1-58113-879-2/04/0011…$5.00.hundreds of nodes, while being robust to network topology changes and link and node failures. The proposed algorithm compensates for the relevant error sources by utilizing the concepts of MAC layer time-stamping [3], [7] and skew compensation with linear regression [2]. While these ideas have been utilized before, their unique combination and its effective implementation yield significantly better precision and somewhat lower communication overhead than existing approaches on the same platform. Finally, the implicit dynamic topology management of the FTSP provides rapid convergence and robustness.The algorithm was implemented on Mica/Mica2 platforms running the TinyOS operating system [4]. A short overview of the target platform is given in Section 2. We offer a survey of existing time synchronization algorithms, emphasizing the algorithms utilizing similar ideas as FTSP, in Section 3. The possible sources of errors of radio message based synchronization are described and analyzed in Section 4. We describe the proposed FTSP algorithm in details and evaluate it based on a large scale experiment in Section 5. In Section 6, we compare FTSP to existing algorithms. Finally, an application using FTSP is described in Section 7 and we offer our conclusions and plans for further improvements in Section 8.2.THE TARGET PLATFORMOne of the most widely used WSN platforms is the Berkeley Mica2 mote [19], [4]. The Mica2 mote has a 7.37 MHz processor, 4 kB of RAM, 128 kB of flash memory, 433 MHz wireless radio transceiver (38.4 kbps transfer rate, 500 feet maximum range), and is powered by two AA batteries. Pluggable sensor boards with temperature, light, magnetic and other sensors are available.The Berkeley motes run the TinyOS operating system [4], [17], an open source, event driven and modular OS designed to be used with networked sensors. TinyOS handles task scheduling, radio communication with error detection, clocks and timers, ADC, I/O and EEPROM abstractions, and power management. Application developers can select a subset of the modules implementing these functionalities, extend or override them if necessary, and statically compile them into the final executable.3.APPROACHES TO TIME SYNCHRONIZATIONTime synchronization algorithms providing a mechanism to synchronize the local clocks of the nodes in the network have been extensively studied in the past. The most widely adapted protocol used in the internet domain is the Network Time Protocol (NTP) devised by Mills [11]. The NTP clients synchronize their clocks to the NTP time servers with accuracy in the order of milliseconds by statistical analysis of the round-trip time. The time servers are synchronized by external time sources, typically using GPS. The NTP has been widely deployed and proved to be effective, secure and robust in the internet. In WSN, however, non-determinism in transmission time caused by the Media Access Channel (MAC) layer of the radio stack can introduce several hundreds of milliseconds delay at each hop. Therefore, without further adaptation, NTP is suitable only for WSN applications with low precision demands.Two of the most prominent examples of existing time synchronization protocols developed for the wireless sensor network domain are the Reference Broadcast Synchronization (RBS) algorithm [2] and the Timing-sync Protocol for Sensor Networks (TPSN) [3].In the RBS, a reference message is broadcasted. The receivers record their local time when receiving the reference broadcast and exchange the recorded times with each other. The main advantage of RBS is that it eliminates transmitter-side non-determinism. The disadvantage of the approach is that additional message exchange is necessary to communicate the local time-stamps between the nodes. To our best knowledge the algorithm has not been extended to large multi-hop networks.The TPSN algorithm first creates a spanning tree of the network and then performs pairwise synchronization along the edges. Each node gets synchronized by exchanging two synchronization messages with its reference node one level higher in the hierarchy. The TPSN achieves two times better performance than RBS by time-stamping the radio messages in the Medium Access Control (MAC) layer of the radio stack [3] and by relying on a two-way message exchange. The shortcoming of TPSN is that it does not estimate the clock drift of nodes, which limits its accuracy, and does not handle dynamic topology changes.4.UNCERTAINTIES IN RADIO MESSAGE DELIVERYNon-deterministic delays in the radio message delivery in WSN can be magnitudes larger than the required precision of time-synchronization. Therefore, these delays need to be carefully analyzed and compensated for. We shall use the following decomposition of the sources of the message delivery delays first introduced by Kopetz and Ochsenreiter [7], [8] and later extended in [3] and [5].(1)Send Time—time used to assemble the message and issue thesend request to the MAC layer on the transmitter side.Depending on the system call overhead of the operating system and on the current processor load, the send time is nondeterministic and can be as high as hundreds of milliseconds.(2)Access Time—delay incurred waiting for access to thetransmit channel up to the point when transmission begins.The access time is the least deterministic part of the message delivery in WSN varying from milliseconds up to seconds depending on the current network traffic.(3)Transmission Time—the time it takes for the sender totransmit the message. This time is in the order of tens of milliseconds depending on the length of the message and the speed of the radio.(4)Propagation Time—the time it takes for the message totransmit from sender to receiver once it has left the sender.The propagation time is highly deterministic in WSN and it depends only on the distance between the two nodes. This time is less than one microsecond (for ranges under 300 meters).(5)Reception Time—the time it takes for the receiver to receivethe message. It is the same as the transmission time. The transmission and reception times overlap in WSN as pictured in Figure 1.(6)Receive Time—time to process the incoming message and tonotify the receiver application. Its characteristics are similar to that of send time.Figure 1.Decomposition of the message delivery delay over a wireless link.The RBS approach completely eliminates the send and access times, and with minimal OS modifications it is also possible to remove the receive time uncertainty. This leaves the mostly deterministic propagation and reception time in wireless networks as the sole source of error. The main strength of RBS is its broad applicability to commodity hardware and existing software in sensor networks as it does not need access to the low levels of the operating system.As the authors of the TPSN protocol observed, on typical WSN platforms, such as the Mica2 mote, one has direct access to the MAC layer, and message time-stamping can be performed during message transmission and reception. This immediately eliminates the same three main sources of uncertainties as in RBS. With a two-way handshake of synchronization messages the TPSN protocol eliminates the unknown propagation time as well.Both the RBS and TPSN protocols suffer from the uncertainties of the overlapping transmission and reception times. To fully understand the constituents of this uncertainty we shall describe the message propagation in a typical wireless channel in more detail. We imagine an idealized point of the transmitted message, such as the end of a particular byte of the message. Then we follow the transmission of this idealized point through the software, hardware and physical levels of the wireless channel from the sender to the receiver.First, the message is transferred to the radio chip piece by piece, usually in a byte oriented fashion. The radio chip signals the microcontroller that it is ready to obtain the next piece. The radio chip then encodes the pieces and generates an electromagnetic wave through the antenna. This wave propagates through space and the receiver’s radio chip converts it back to binary representation. Then the radio chip on the receiver side signals the microcontroller that a new piece of data is ready and can be read through some protocol. Therefore, we have the following delivery delays of an idealized point of the message.(7)Interrupt Handling Time—the delay between the radio chipraising and the microcontroller responding to an interrupt.This time is mostly less than a few microsecond (waiting for the microcontroller to finish the currently executed instruction), however when interrupts are disabled this delay can grow large.(8)Encoding Time—the time it takes for the radio chip toencode and transform a part of the message to electromagnetic waves starting from the point when it raised an interrupt indicating the reception of the idealized pointfrom the microcontroller. This time is deterministic and is in the order of a hundred microseconds.(9)Decoding Time—the time it takes for the radio chip on thereceiver side to transform and decode the message from electromagnetic waves to binary data. It ends when the radio chip raises an interrupt indicating the reception of the idealized point. This time is mostly deterministic and is in the order of hundred microseconds. However, signal strength fluctuations and bit synchronization errors can introduce jitter.Some radio chips cannot capture the byte alignment of the transmitted message stream on the receiver side and the radio stack has to determine the bit offset of the message from the alignment of a known synchronization byte and then shift the message accordingly. Since the transmission time of the byte is a few hundred microseconds at 38.4 kbps, the delay caused by the incorrect byte alignment must be compensated for. This compensation is performed by the implementation of TPSN on the Mica2 platform, but it is not reported in [3].(10)Byte Alignment Time—the delay incurred because of thedifferent byte alignment of the sender and receiver. This time is deterministic and can be computed on the receiver side from the bit offset and the speed of the radio.Figure 2.The timing of the transmission of an idealized point in the software (cpu), hardware (radio chip) and physical (antenna) layers of the sender and the receiver.Figure 2 summarizes the decomposition of delivery delay of the idealized point of the message as it traverses over a wireless channel. Each line represents the time line of the layer as measured by an ideal clock. The dots represent the time instance when the idealized point of the message crosses the layers. The triangles on the first and last line represent the time when the cpu makes the time-stamps. Depending on the specific hardware the time stamp is usually recorded by the microcontroller when it handles the radio chip interrupts both on the sender and receiver sides. Alternatively, capture registers provided by some hardware can be employed to eliminate the interrupt handling time. We do not consider the effect of various coding techniques, such as Manchester or SECDEC coding or forward error-correction schemes, to the timing of message transmission. The codes usedin practice are block codes, and we can assume that the idealized point of the message is at a block boundary.On the Mica2 platform, the interrupt handling time is typically around 5µs depending on the length of the code path between the start of interrupt handler and the part that records the local time. However, we observed interrupt handling times as high as 30µs. The sum of encoding and decoding times is between 110µs and 112µs. The byte alignment time is between 0µs (for bit offset 0) and 365µs (for bit offset 7). In contrast, the propagation time is under 1µs. Table 1 summarizes the magnitudes and distribution of the various delays in message transmissions.Table 1.The sources of delays in message transmissions Time Magnitude DistributionSend and Receive 0 – 100 ms nondeterministic,depends on theprocessor loadAccess 10 – 500 ms nondeterministic,depends on thechannel contentionTransmission / Reception 10 – 20 ms deterministic,depends on messagelengthPropagation < 1µs for distancesup to 300 meters deterministic, depends on the distance between sender and receiverInterrupt Handling < 5µs in mostcases, but can be ashigh as 30µsnondeterministic,depends on interruptsbeing disabledEncoding plus Decoding 100 – 200µs,< 2µs variancedeterministic,depends on radiochipset and settingsByte Alignment 0 – 400µs deterministic, can becalculatedUsing our definitions we can properly express the sources of time-stamping errors of the RBS and TPSN algorithms. The RBS protocol is sensitive to the propagation, decoding and interrupt handling time differences between the two receivers. The main source of error here is the jitter in interrupt handling and decoding. The TPSN protocol is sensitive to the encoding, decoding and interrupt handling time differences between the sender and receiver. Note that although the propagation time has been eliminated, the encoding and decoding times are not because they might not be the same on the sender and receiver side. It is important to point out that both the RBS and TPSN protocols suffer from the two largest sources of uncertainty of MAC layer time-stamping: the jitter of interrupt handling and decoding time. On the other hand, as we will see in the next section, the FTSP time-stamping protocol effectively reduces all sources of time-stamping errors except for the propagation time.5.FLOODING TIME SYNCHRONIZATION PROTOCOLThe goal of the FTSP is to achieve a network wide synchronization of the local clocks of the participating nodes. We assume that each node has a local clock exhibiting the typical timing errors of crystals and can communicate over an unreliable but error corrected wireless link to its neighbors.The FTSP synchronizes the time of a sender to possibly multiple receivers utilizing a single radio message time-stamped at both the sender and the receiver sides. MAC layer time-stamping can eliminate many of the errors, as observed in [16] and [3]. However, accurate time-synchronization at discrete points in time is a partial solution only. Compensation for the clock drift of the nodes is inevitable to achieve high precision in-between synchronization points and to keep the communication overhead low. Linear regression is used in FTSP to compensate for clock drift as suggested in [2].Typical WSN operate in areas larger than the broadcast range of a single node; therefore, the FTSP provides multi-hop synchronization. The root of the network—a single, dynamically (re)elected node—maintains the global time and all other nodes synchronize their clocks to that of the root. The nodes form an ad-hoc structure to transfer the global time from the root to all the nodes, as opposed to a fixed spanning-tree based approach proposed in [3]. This saves the initial phase of establishing the tree and is more robust against node and link failures and dynamic topology changes.5.1Time-stampingThe FTSP utilizes a radio broadcast to synchronize the possibly multiple receivers to the time provided by the sender of the radio message. The broadcasted message contains the sender’s time stamp which is the estimated global time at the transmission of a given byte. The receivers obtain the corresponding local time from their respective local clocks at message reception. Consequently, one broadcast message provides a synchronization point (a global-local time pair) to each of the receivers. The difference between the global and local time of a synchronization point estimates the clock offset of the receiver. As opposed to the RBS protocol, the time stamp of the sender must be embedded in the currently transmitted message. Therefore, the time-stamping on the sender side must be performed before the bytes containing the time stamp are transmitted.Figure 3.Data packets transmitted over the radio channel. Solid lines represent the bytes of the buffer and the dashed lines are the bytes of packets.Message broadcast starts with the transmission of preamble bytes, followed by SYNC bytes, then with a message descriptor followed by the actual message data, and ends with CRC bytes. During the transmission of the preamble bytes the receiver radio synchronizes itself to the carrier frequency of the incoming signal. From the SYNC bytes the receiver can calculate the bit offset it needs to reassemble the message with the correct byte alignment. The message descriptor contains the target, the length of the data and other fields, such as the identifier of the application layer thatneeds to be notified on the receiver side. The CRC bytes are used to verify that the message was not corrupted. The message layout is summarized in Figure 3.The FTSP time-stamping effectively reduces the jitter of the interrupt handling and encoding/decoding times by recording multiple time stamps both on the sender and receiver sides. The time stamps are made at each byte boundary after the SYNC bytes as they are transmitted or received. First, these time stamps are normalized by subtracting an appropriate integer multiple of the nominal byte transmission time, the time it takes to transmit a byte. The jitter of interrupt handling time is mainly due to program sections disabling interrupts on the microcontroller for short amounts of time. This error is not Gaussian, but can be eliminated with high probability by taking the minimum of the normalized time stamps. The jitter of encoding and decoding time can be reduced by taking the average of these interrupt error corrected normalized time stamps. On the receiver side this final averaged time stamp must be further corrected by the byte alignment time that can be computed from the transmission speed and the bit offset. Note that, even though multiple time stamps are made, only the final error corrected time stamp is embedded into the message. The number of bytes put an upper limit on the achievable error correction using this technique. However, with only 6 time stamps, the time-stamping precision can be improved from tens of microseconds to 1.4µs on the Mica2 platform as measured by the following experiment.Four motes were sending time-stamped messages to each other for 10 minutes, each with a 5-second sending period. The time-stamps were recorded both on the sender and receiver sides, and the pairwise clock offset and skew values were determined off-line with linear regression. The time-stamping error is the absolute value of the difference of the recorded receiver side time stamp and the linearly corrected sender side time-stamp. The average and maximum time-stamping errors were 1.4µs and 4.2µs, respectively. Since the FTSP time-stamping employs a single radio message, it does not and cannot compensate for the propagation delay. This is not a major limitation of the approach in typical WSN, however, as the propagation delay is less than 1µs for up to 300 meters.5.2Clock drift managementIf the local clocks had the exact same frequency and, hence, the offset of the local times were constant, a single synchronization point would be sufficient to synchronize two nodes. However, the frequency differences of the crystals used in Mica2 motes introduce drifts up to 40µs per second. This would mandate continuous re-synchronization with a period of less than one second to keep the error in the micro-second range, which is a significant overhead in terms of bandwidth and energy consumption. Therefore, we need to estimate the drift of the receiver clock with respect to the sender clock.The offset between the two clocks changes in a linear fashion provided the short term stability of the clocks is good. We verified the stability of the 7.37 MHz Mica2 clock by periodically sending a reference broadcast message that was received by two different motes. The two motes time-stamped the reference message using the FTSP time-stamping described in the previous section with their local time of arrival and reported the time-stamp. For each transmitted message the offset of the two reported time-stamps was calculated. The offsets were further examined: linear-regression was used to find the line L best approximating the dataset and the errors were analyzed. For a data point (time,offset) and the regression line L, the error is offset-L(time). A one hour experiment produced the following results: the average value of the absolute errors was 0.95µs and the maximum absolute error was 4.32µs. The distribution of the errors, calculated off-line is shown in Figure 4. This off-line regression provides the best prediction that can possibly be achieved, provided the clocks can be considered stable during the experiment. Naturally this method cannot be used online; it is used here as a reference to evaluate online solutions.Figure 4.The distribution of the errors of linear-regression (LR): off_line refers to off-line LR, 30sec refers to time sync interval P=30s, query interval 18s, and 300sec refers to time sync interval P=300s, query interval 93s.We need to identify the trend of the global time relative to the local time from the data points received in the past. Furthermore, only a limited number of data points can be stored due to the memory constraints of the platform. The following scenario was used to test our Mica2 implementation: mote A maintains the global time and sends synchronization messages to mote B with a period of T. Mote B estimates the skew and offset of its local clock from that of A using linear regression on the past 8 data points. A reference broadcaster sends a query message with period t and both A and B respond to this query by time-stamping itsarrival with the global time and reporting it to the base station. Figure 5.Time synchronization error between two motes. The time synchronization was stopped after 30 minutes. The initial small error of the skew estimate results in increasing synchronization error over time.The linear regression prediction error is the difference between the global time given by A and the estimated global time given by B. Figure 4 shows the distribution of these prediction errors, for (a) T=30s, t=18s, and (b) T=300s, t=93s. The length of experiment (a) was 18 hours, the average absolute error was 1.48µs, and the maximum absolute error was 6.48µs. The length of experiment (b) was 8 hours, the average absolute error was 2.24µs and the maximum absolute error was 8.64µs.An important design parameter is the required resynchronization interval to reach the desired precision. As shown in Figure 4, the 30s resynchronization interval gave slightly better results than 300s. To further evaluate the behavior of the skew compensation, another experiment was carried out, the results shown in Figure 5. This result shows that the resynchronization period, depending on the accuracy requirements, can go up to several minutes.5.3Multi-hop time synchronizationIn practical WSN applications, the network radius is greater than one hop. If network-wide synchronization is required, the multi-hop FTSP protocol can be used, as described in this section. The only assumption the protocol makes is that every node in the network has a unique ID.Nodes in multi-hop FTSP utilize reference points to perform synchronization. A reference point contains a pair of global and local time stamps where both of them refer to the same time instant, as described in Section 5.1. Reference points are generated by sending and receiving periodic broadcast messages, which are either transmitted by the synchronization-root (root, for short), or any synchronized node in the network. The root is a special node, elected and dynamically reelected by the network, to which the whole network is being synchronized. A node that is in the broadcast radius of the root can collect reference points directly from it. Nodes outside the broadcast radius of the root can gather reference points indirectly through other synchronized nodes that are located closer to the root. When a node collects enough consistent reference points, it estimates the offset and skew of its own local clock, as described in Section 5.2, and becomes synchronized. The newly synchronized node can then broadcast synchronization messages to other nodes in the network. In the following subsections the most important aspects of the protocol will be presented.Synchronization Message Format: Each synchronization message contains three fields: the timeStamp, the rootID, and the seqNum. The timeStamp contains the global time estimate of the transmitter when the message was broadcasted. The rootID field contains the ID of the root, as known by the sender of the message. The seqNum is a sequence number set and incremented by the root when a new synchronization round is initiated. Other synchronized nodes insert the most recent (i.e. the largest) received seqNum into the synchronization messages they broadcast. This field is used to handle redundant synchronization messages.Managing Redundant Information: Since all synchronized nodes periodically transmit synchronization messages, in a dense network a receiver may receive several messages from different nodes in a short time interval. Due to limited resources, an appropriate subset of the messages must be selected to create reference points. In the Mica2 implementation an eight-element regression table stores the selected reference points used to calculate the regression line, and, thus, the drift of the local clock. To achieve more accurate offset and skew estimation using the limited amount of data that can be stored in the regression table, it is more beneficial to store reference points that are distributed over a longer period of time. To aid message filtering, each node maintains a highestSeqNum variable. Also each node has a myRootID variable, containing the root ID as known by the node.A received synchronization message is used to create a reference point only if the rootID field of the message is less than or equal to myRootID and the seqNum field is greater than highestSeqNum in the case when rootID = myRootID. The node’s variables are updated after storing a reference point, according to the respective fields in the message. This message filtering protocol guarantees that only the first message arrived will be used in the reference table for each rootID and seqNum pair (i.e. one per round), providing reference points distributed over a longer time period for more accurate skew and offset estimation. The pseudo-code describing this protocol is presented at lines 3–9 in Figure 6 and 11–16 in Figure 7.The root election problem: To perform global synchronization, obviously one and only one root is needed in the network. Since nodes may fail or the network can get disconnected, no dedicated node can play the role of the root. Thus a robust election process is needed to provide a root after startup, and also in case of root failure. FTSP utilizes a simple election process based on unique node IDs, as follows:Figure 6.The handling of new synchronization messages. When a node does not receive new time synchronization messages for ROOT_TIMEOUT number of message broadcast periods, it declares itself to be the root (myRootID := myID). Thus after a ROOT_TIMEOUT period, there will be at least one, but possibly multiple roots in the network. Whenever a node receives a message with a rootID field smaller than its myRootID variable, it updates the variable according to the received rootID field. This mechanism ensures that roots with higher IDs give up their status and eventually there will be only one root—the node with the smallest ID—in the whole network. The pseudo-code describing1 event Radio.receive(TimeSyncMsg *msg)2 {3 if( msg->rootID < myRootID )4 myRootID = msg->rootID;5 else if( msg->rootID > myRootID6 || msg->seqNum <= highestSeqNum )7 return;89 highestSeqNum = msg->seqNum;10 if( myRootID < myID )11 heartBeats = 0;1213 if( numEntries >= NUMENTRIES_LIMIT14 && getError(msg) > TIME_ERROR_LIMIT )15 clearRegressionTable();16 else17 addEntryAndEstimateDrift(msg);18 }。

《面向稀疏样本的WiFi室内定位算法研究》篇一一、引言随着无线通信技术的飞速发展，WiFi室内定位技术逐渐成为研究的热点。

然而，在面对稀疏样本的条件下，传统的室内定位算法往往无法实现精确的定位。

因此，研究并优化面向稀疏样本的WiFi室内定位算法具有重要的实际意义和应用价值。

本文将就稀疏样本条件下的WiFi室内定位算法进行深入研究，并提出相应的优化策略。

二、WiFi室内定位技术概述WiFi室内定位技术主要通过接收来自多个WiFi接入点的信号强度信息，结合信号传播模型和算法处理，实现对目标位置的精确估计。

然而，在实际应用中，由于室内环境的复杂性和动态性，以及WiFi信号的多径传播和衰减等因素的影响，使得定位精度受到一定程度的限制。

特别是在稀疏样本条件下，传统算法的定位效果往往不尽如人意。

三、稀疏样本对WiFi室内定位的影响在稀疏样本条件下，传统WiFi室内定位算法面临的主要问题包括：样本数据不足、特征提取困难、算法泛化能力差等。

具体而言，由于样本数据稀疏，导致信号强度信息不充分，难以准确反映室内环境的实际情况；同时，特征提取的难度增加，使得算法在处理稀疏样本时难以有效提取有用的信息；此外，算法的泛化能力也会受到影响，难以适应不同环境和场景的变化。

四、面向稀疏样本的WiFi室内定位算法研究针对稀疏样本条件下的WiFi室内定位问题，本文提出了一种基于深度学习的优化算法。

该算法通过构建深度神经网络模型，实现对WiFi信号强度的学习和特征提取。

具体而言，算法利用大量的训练数据对神经网络进行训练，使其能够学习到WiFi信号强度与位置信息之间的非线性关系；同时，通过优化神经网络的架构和参数，提高算法的泛化能力，使其能够适应不同环境和场景的变化。

五、实验与分析为了验证本文提出的算法的有效性，我们进行了大量的实验。

实验结果表明，在稀疏样本条件下，本文提出的算法能够显著提高WiFi室内定位的精度和稳定性。

与传统的WiFi室内定位算法相比，本文提出的算法在定位精度和鲁棒性方面均有所提升。