`

`'DfsTRIBUTED
`
`SENSO]R NETS
`
`Proceedings of a Workshop
`held at
`Carnegie-Mellon University
`December 7-8, 1978
`
`Sponsored by the
`Defense Advanced Research Projects Agency
`
`A limited number of copies
`are available from the
`Computer Science Department
`Carnegie-Mellon University
`Pittsburgh, PA 15213
`
`The views and conclusions contained in this document are those of the authors and should
`not bo interpreted as necessarily representing the offici al policies. either expras~ed or
`implied of the Defense Advanced Research Agency or the United Stites Government.
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 2
`
`

`

`|PR2020-00910
`
`Garmin, et al. EX1021 Page 3
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 3
`
`

`

`TABLE OF CONTENTS
`
`SESSION 1:: SYSTEM ORGANIZATION
`
`OSN Prob l ems -- An Overv iew
`Je ff rey A. Barnet t
`USC/I n f orma ti on Sc i ences Inst i tute
`
`Strai.,man Des i gn for a OSN to Detec t and Track LoLJ F lying Aircraf t
`R. Lacoss and R. Wa lton
`MI T/ L i nco l n Laboratory
`
`Di s t r i bu t ed Sensors N·et1Jorks {OSN): An Attempt t o Def ine the Issues
`Yechi -:lm Yem i n i
`USC/I n f ormat i on Sc iences Inst itu t e
`
`Commen t s on Lo1,,1 Al ti t ude Air Defense Systems
`J ohn F i e ldi ng
`MIT/ L inco ln Laboratory
`
`SESSION ll:: SENSOR TECHNOLOGY
`
`Sensor Tutor i a l
`R. Lacoss
`MIT / L i nco ln Laboratory
`
`Mu lti s ite Acoust i c Locat ion
`Rober t Wa I ton
`MIT /L i nco ln Laboratory
`
`Lor:,g Ran·ge Acoust ic Track ing of Lo1,,1 Flying Aircraft
`T. E. landers and R. T. Lacoss
`MIT / L i nco ln Laboratory
`
`SESSION ill~ COMMUNICATION TECHNOLOGY
`
`Hi gh-Leve l Protoco l s
`Rober t F . Sproul I and Dan Cohen
`Carneg i e-Me l Ion Un i versity & USC/I nfor ma ti on Sc iences Inst itute
`
`Pr otoc ol s for OSN
`Danny Cohen
`USC/I nformat i on Sc i ences Ins titute
`
`(Abs t ract on ly)
`
`i
`
`37
`
`41
`
`53.
`
`152
`
`61
`
`63
`
`68
`
`78
`
`124
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 4
`
`

`

`SESSION IV : PROCESSING TECHNIQUES AND ALGORITHMS
`
`Tutor i al Survey of Algor i thms for Locat ing and Ident ifying Spat ial ly
`Di stributed Sources and Rece ivers
`M. Mor f , 8 . Fr iedlander and J. Newk irk
`Stanford Universi ty
`
`S i ng l e - S i te O~tect ion and Target Parameter Est imat ion
`Paul Demko. Jr.
`MIT/L inco l n Laboratory
`
`Posit i 9n Locat i on in a TOMA Network
`Stephen Cable
`Rockwel I Interna ti onal
`
`The Pos i t i on ing Prob lem - A Draf t of an In t ermediate Summary
`Yech i am Yem ini
`USC/Infor mation Sciences Inst i tute
`
`SESSION Y. : DISTRIBUTED SOFTWARE
`
`Dynam i ca ll y Modifiable Distr i buted Systems
`A. N. Habermann
`Carneg i e - Me l Ion University
`
`Language Design for Di str ibuted Systems
`Peter Hi bbard
`Carneg i e-Me l Ion University
`
`.
`
`SESSION Vl : RELATED AI RESEARCH
`
`What Language Unders t and ing Research Sugges t s About Distr ibuted Al
`Earl O. Sacerdot i
`SRI
`I nterna t i ona I
`
`The Deve l opmen t of a Mult i -Sensor System for Assess ing a Threat
`Order of Batt le
`Thomas D. Garvey and Mart in A. Fi schler
`SRI Internat iona l
`
`94
`
`105
`
`1
`
`137
`
`111
`
`151
`
`8
`
`146
`
`App l i ca t lon of Knowledge Based Programm ing to Signal Understanding Systems
`Corde l I Green and Br i an P. McCune
`Sys t ems Contro l , Inc.
`
`115
`
`ii
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 5
`
`

`

`Surve i I l ance In t egrat ion Automat ion Pro jec t {SIAP}
`Rober t J . Orazov ich and Scott i e Brooks
`Sys t ems Contro l , Inc.
`
`Mach i ne Recogn it ion and Understanding of Manual Morse
`Al ber t Vezza e t. a l .
`MIT / L i nco ln Laboratory
`
`SESSION Vtl = DlSTRIBUTED Al
`Applicat i ons of the Contract Net Frame~ork: Distributed Sensing
`Reid G. Smi t h and Randal I Davis
`Stanford Un i vers ity
`
`Funct i onal ly Accurate Distr ibuted Prob lem Solv i ng Systems
`Vi c t or A. Lesser and Dan i e l O. Corki I I
`Univers it y of Massachusetts at Amherst
`
`Di s t r ibuted [n t el I i gence for Si t uat ion Assessment
`F. Hayes-Roth and R. ~esson
`The Rand Corporat ion
`
`119
`
`125
`
`12
`
`21
`
`27
`
`i ii
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 6
`
`

`

`Barnett, Jeffrey A.
`
`Brooks, Scottie
`
`Cable, Stephen
`
`Cohen, Dan
`
`Corkill, Daniel 0.
`
`Davis., Randall
`
`Demko Jr., Paul
`
`Orazovich, Robert J.
`
`Fief ding, John
`
`Fischler, Martin A.
`
`Friedlander, 8.
`
`Garvey, Thomas
`
`Green, Cordell
`
`Habermann, A. N.
`
`Hibbard, Peter
`
`Hayes-Roth, F.
`
`Lacoss, R.
`
`Landers, T. E.
`
`Lesser, Victor R.
`
`McCune, Brian P.
`
`Morf, M.
`
`Newkirk, J.
`
`Sacerdoti, Earl 0.
`
`Smith, Reid G.
`
`Sproull, Robert F.
`
`Vezza, Albert
`
`Walton, R.
`
`Wesson, R.
`
`Yemini, Yechiam
`
`AUTHOR INCEX
`
`iv
`
`37
`
`119
`
`l
`
`78,124
`
`21
`
`12
`
`105
`
`119
`
`152
`
`146
`
`94
`
`146
`
`115
`
`111
`
`151
`
`27
`
`41, 61, 68
`
`68
`
`21
`
`115
`
`94
`
`94
`
`8
`
`12
`
`78
`
`125
`
`41, 63
`
`27
`
`53,. 137
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 7
`
`

`

`

`

`

`

`Analysis and simulation results indicate that the active
`mode range measurements produce better performance
`that is less dependent upon the geometry oC the sources
`than for the passive mode case. However, there are rea(cid:173)
`sons for choosing to use the passive mode at the e.,cpense
`of degraded performance. In an operational scenario.
`some umts may be required to operate in a radio silent
`mode. :\t the same time, it ma y be import.ant ior these
`units to include position information in thelt' infrequent
`transm1SS1ons. Such units would certainly operate in the
`passive mode. Another important consideration is the
`amount of network traffic required for position location.
`[f network capacity is a problem and an adequate source
`geometry is available, then assigning some units to the
`passive mode can reduce the traffic requirements. An(cid:173)
`other solution to this problem is the use of a hybrid mode
`employing active time measurements with passive position
`measurements. ..\ discussion of the hybrid mode is beyond
`the scope oi this paper. In an attempt to satisfy accuracy
`requirements. capacity limitations and operational objec(cid:173)
`tives. a typical network may include a cuve mode units,
`passive mode units, a nd hybrid mode uruts.
`Kalman Filter
`
`In order to successfully track the clock and the position
`of a unit usuig noisy measurements and to e.,ctrapolate
`time and position between sets oi measurements. a state
`model of the clock and the dynamics of the unit must
`be maintained. Thus. once position and time estimates
`have been obtained Crom the solution to the linearized
`multilateration equations. thLS new estimate must be
`combined with the previous estimates to update the state
`model. A Kalman !ilter was seleeted to track the state
`oi the system. ..\ Kalman filter provides Improved per(cid:173)
`for mance over simpler fixed gain filters (eg ci • - p tracker)
`and it provides Uie error covariance matnx necessary
`to implement the covariance de iined hierarchy descnbed
`below. The Kalman filter is defined by the state model
`·description of the system and the error-corrupted mea(cid:173)
`sure ments which are available for updating the model.
`For a ground. mobile network. a six-dimensional state
`vector has been demonstrated to provide an adequate
`state model. The six components are clock offset. clock
`driit rate. x-<lirection position. y-<lirection position. x(cid:173)
`direcuon velocity, and y-<lirection velocity. This model
`assumes tr.at altitude is provided from an e.,ctemal mea(cid:173)
`surement. independently from the position location iunc(cid:173)
`tion.
`:\ variant of the above state veetor would use
`heading and velocity in place of velocity in the x and y
`directions. The measurement used by the Kalman tilter
`would be the solution to the linearized multilateration
`equations and its associated covariance matrL'C. Platforms
`exhibiting higher mobility, eg aircraft. would require an
`extended state vector and additional measurements from
`onboard navigation equipment in order to successiully
`track the platfor m.
`
`Given a measurement and its variance. a Kalman filter
`attemots to update the state model in a way such that the
`trace oi the covariance matrix of the state vector is mini(cid:173)
`mized. The basic Kalman filter equations are summarized
`below:
`
`Extraoolation
`
`! (ext) = A ! (old)
`
`C (ext) = A C (old)A T
`
`Update
`
`! (new) = A! (old)· K (new) [ ! (new) - HA! (old)l
`K (new) = C (ext) HT [ H C (ext) BT - R (new>r1
`
`C (new) = C (ext) - K (new) H C (ext)
`
`where
`
`!
`
`A
`
`C
`
`K
`
`!
`
`H
`
`R
`
`= state vector
`
`= state transition matrix
`
`= state vector error covariance matrix
`
`= Kalman filter gain matrix
`
`= measured values
`= linear transformation from ! to ;
`
`= measurement erroc- covariance matrix.
`
`These Kalman· filter equations and the multilateration
`measurements provide the oasis for tracking the relative
`position of network elements.
`
`~etwork Architecture
`
`The ability of each network element to perform position
`location is dependent upon the existence of a common
`relative grid and the reception of an adequate number
`of useable position reports. The network structure oi
`the position location function should per form four major
`tasks. Those tasks are:
`
`a. Support time synchronization in the network
`
`b. Establish a rectilinear coordinate grid for relative
`navigation
`
`c. Ensure an adequate supply of position reports to sup(cid:173)
`port any unit attempting to perform position location
`
`d.
`
`Provide for stability and robustness of the position
`location iunction.
`
`Due to the interrelationship between time synchronization
`and position location. any networlC structure which per(cid:173)
`forms the last three taSks will support time synchromza(cid:173)
`tion in the network. For applications where relative
`navigation 15 not required. the position location algorithms
`can provide time tracking only. The clock offset measure(cid:173)
`ments can be provided by active mode measurements
`without pos1t1on or oy passive mode measurements with
`a rough position estimate.
`
`In conjunction with the network initialization ;:,rocedure.
`the :x,s1t1on location network strUcture should de fine
`a reiative rectilinear grid and. if ?OS5ible. a geode tic
`grid. Some of the network elements are given the re(cid:173)
`sponsibility for establishing the grid. These elements
`are:
`
`a.
`
`:.taster l:nit ( ~IU). An element whose relative posi(cid:173)
`tion is defined to oe the or igin of the grid.
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 10
`
`

`

`

`

`

`

`

`

`Conclusion
`
`In summary. usable position accuracies can be obtained
`within a TDMA network. A position location algorithm
`utilizmg multilaterauon and a Kalman filter linear esti(cid:173)
`mator can track the position and clock otcset withm each
`network element. An analysis of this method shows that
`performance LS a complex function of a number o( factors.
`With the tools which have been developed for analyzing
`performance. the obtainable accuracy can be pre<iicted
`or the parameters reqwred to meet a performance goal
`can be chosen. given a particular scenario. The cost of
`implementing position location in t~ms of network
`throughput and hardware compleicity should not be un(cid:173)
`reasonable. Consequently, position location may be a
`valuable. obtainable addition to a tactical data distri(cid:173)
`bution networK.
`
`REFERENCES
`
`l.
`
`''Feasibility of Position Location in a UPR Network",
`Collins Quarterly Technical Report, Pocket Radio
`Communications. Telecommunications Systems Div1-
`'sion. Rockwell International. August 1978.
`
`2.
`
`Fried. W. R .• "Prmciples and Simulation of JTIDS
`Relative Navigation", IEEE Trans. AES. Vol. AES- 14,
`No. 1. January 1978.
`3. Snodgrass. R. c., "Recursive Navigation Algorithm
`for Electronic Grid lntegrauon", The :\IITRE Cor(cid:173)
`poration Teclulical Report :\1TR-2821. April. 1974.
`
`4. Snodgrass. R. C .. "Range Determination and Synchmi(cid:173)
`zation in SEEK suss~. The ~UTRE Corporation Work(cid:173)
`ing Paper WP-5447, Feoruary, 1975.
`
`5. Rome. R. J. and Stambaugh, J. S., ~Evaluation of
`the Accuracy oi Community Relative Navigation
`Organization Concepts", Navigauon: Journal of the
`lnsutute of Navigation. VoL 24 ~o. 2, Summer 1977.
`
`6. Ricke. G. G. and Williams. J. R .. ''Adaptive Tracking
`Filter ior \laneuvering Targets'. IEEE Trans. on . .\ES.
`Vol. AES- 14. No. l January 1978.
`
`, . Sage. A. P. and :\1elsa. J. L .. Estimation Theorv with
`.\oolications to Communications ano Control, ~tcGraw(cid:173)
`Hill Book Company, 1971, pp J'."6-US.
`
`'
`
`j
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 14
`
`

`

`

`

`

`

`

`

`

`

`

`

`execution of the announced task. A manager may receive
`s everal sucn bids in response to a single task announcement:
`based on th e Information In the bids, It selects one (or
`several) node(s) for execution of the task. The selection Is
`communicated to the successful b1dder(s) through an award
`message. These selected nodes a.ssume respons1brlity for
`execution of t he task, and each Is called a cantractM tor
`that t ask.
`
`A c ontract Is thus an explicit agreement between a
`node that generates. a task (the manager) and a node that
`executes the task ( the contractor). Note th at establishing a
`contract
`l:s a proceu of mutual selection. Al(ailable
`contractors evaluate task announcements made by several
`managers until they f ind one of Interest; the managers then
`evaluete the bids received from potential contractors and
`select one t hey determine to be most appropriate. Both
`parties to the agreement have evaluated the Information
`supplied by the other and a mutual selec~ been made.
`
`The contract negotiation process Is expedited by three
`forms of t ask•dependent information contained in a t ask
`announcement. An elfg/bl/lty speclfl~ion lists the criteria
`that a node must meet to be eligible to submit a bid. This
`specification reduces mes.sage traffic by pruning nodes
`whose bids would be clearly unacceptable. A tad
`abstraction Is a brief description of
`the
`t ask
`to be
`executed. and allows a potential contractor to evaluatt1 lb
`l evel of interest In executing this task relative to others that
`are available . . An abstraction Is used rather than a complete
`description In order to reduce the length of the message
`( and hence message tratflc).J Anally, a bid sp«:lflcatlon
`d etails the expected fonn of a bid for that task. It enables a
`potential contractor to transmit a bid that contains only a
`bnef specification of its capabilities that are relevant to the
`t ask (this specification is called a node ~•traction), rather
`t han a complete description. This botn simpllfles the task of
`the manager in evaluatfng bids. and further reduces message
`trafflc .4
`
`that
`t he node
`locally by
`Contracts are queued
`generates them until they can be awarded. If no bids are
`received for a contTact by the time an e,cpfratlon time
`(included In the task announcement) has passed. then the
`contract Is re·announced. This proce53 ls repeated until the
`contract can be awarded.5
`
`The award message contains a t ask specification,
`wh1c0h includes the complete specification of the task to be
`executed. After the task has been completed, the contractor
`sends a r eport to Its manager. This message lnctudes a
`result descr/pt/OII. 'Nhich communicates the result~ that
`have been achieved during execution of t he task.
`
`The manager may terminate the execution of contracts
`
`as necessa_ry (with a termination message), and further
`(sub)contracts may be let in tum as required by the size of a
`contract or by a requirement tor special expertlse or data
`that the contractor does not have.
`
`It Is Important to note that individual nodes are not
`designated a priori as manager, or contractors. These are
`only roles, and any node can take on either role. During the
`course of problem solving, a particular node normally takes on
`tor different
`both
`roles
`( perhaps even simultaneously
`contracts). This leads to more efficient utilization of nodes.
`as compared, for example, to schemes that do not allow
`no<l8$ ttiat have contracted out subtasks to take on other
`t asks while they are waiting for results. lndMdual nodes,
`then, are not statically tied to t he control hierarchy.
`
`Idea of transfer of expertise
`Note also that the
`between nodes (via t ransfer of procedures or data) can be
`reedily handled by the protocol. It c an be handled as a
`standard contract between a node
`that announces (In
`effect) I nud tht codt for <prouduu--d,sCTiptton> , and a node
`that bids on the t ask by Indicating that it has the re<1uired
`Information.
`
`To review. the normal method of negoti ating II contract
`is f or a node (called the manager for a task) to Issue a task
`announcement. Many such announcements are made over the
`course of time. Other nodes are listening and submit bids on
`they are suited. The
`those announcements
`for which
`managers evaluate t he bids and award contracts to the most
`suutable nodes (which are then called contractors for the
`awarded tasks).
`
`The normal contract negotiation process can be
`simplified In some instances. with a resulting anhanc-ent In
`t h>e efficiency of the protocol. If II manager knows exactly
`wlnich node ls appropriate for execution of a task, a dlrttcted
`contract
`can
`be
`awarded. This diHers
`the
`from
`announced contract in that no announcement Is made, and no
`bids are submitted. Instead, an ·award Is made directly. In
`such cases, nodes awarded contracts must acknowledge
`receipt and have the option of refusal.
`
`The protocol has also been designed to allow a reversal
`of the normal negotiation process. When the processing load
`on tile net is high. most task announcements will not be
`arnswered with bids because all nodes will be already busy .
`a node
`availability
`Hence
`the
`protocol
`Includes
`announcement message. Such a message can be issued by
`an idle nOde. It is an Invitation tor managers to send task
`announcements or directed contracts to that node.
`
`Finally, for tasks that 11m00nt to simple reciuests tor
`lnfOfmat,on, a contract may not be appropriate.
`In such
`cases. a request • response sequence can be used without
`further embellishment. Such messages (that aid in
`the
`distribution of data as oppased to control) are Implemented
`as request and Information messages. The request message
`Is used to encode stra,gnttorward requests tor information
`for which contracting
`Is unnecessary. The
`Information
`message is used both as a response to a request massage
`and as a general data t ransfer message.
`
`3 One component of the abstraction is the task 11p1, or
`g eneric classification of the task.
`that makes up
`the elfg,b,lity
`4 The
`Information
`speci fication. task abstraction. and bid specification f or any
`given example must be supplied by
`the applications
`programmer. In Section 3 we w1il see examples of this type
`of informs tlon.
`5 The Is a simplified version of the actual process ( and
`does not work in the case of a task that cannot be executed
`due. for example, to tack of sufficient data); see (Smith,
`1978c] for t he compl ete description.
`
`1" . .)
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 20
`
`

`

`

`

`For purposes of this example, the only form of signal
`processing we consider 1s narrow band spectral analysis. The
`:,gnai h as
`the
`following
`features,
`frequency,
`tlrH of
`de tection, strength, characteristics ( e.g., Increasing signal
`strength), name and ~rtlon of the detecting node, and
`n ame. type, and orientation of the detecting sa-.'
`
`contractors that are responsible tor Integration of information
`associated with 1nd1V1dual
`these
`vemcles. Each of
`classif"at1V11
`contractors manages,
`a
`contractor
`that
`/ocaliratitnt contractor,
`d etermines vehicle
`type; a
`thet
`d etermines vehicle position: and a tr!Uhnf contractor, that
`tracks the vehicle as rt passes through the area. 11
`
`Signals are formed Into signal grwps at the second
`l evel of the data hierarchy. A signal group Is a coilectlon of
`r elated signals? For this example, the signal groups have the
`rollowlng features: the funda-ntal frequency of the group,
`the time of group formation. and the f eatures of the signals in
`the group (as above).
`
`group
`
`area
`
`vehi cle
`
`The next level of the hierarchy Is the description of the
`vtiiiclt . It hes one or more signal groups associated with It
`further specified by position. speed, cowae. and
`and Is
`type. 10 Position can be established by triangulatlon, using
`matching groups detec t ed by several sans«s wltn different
`pos1tk>ns and orientations. Speed and coune must be
`established over tim e by tracking.
`
`The arta mat>
`the data
`the next level of
`forms
`tnfonnatlon al>OUt
`the
`Incorporates
`hiera rchy. Thus mep
`vehicle traffic in an area. It Is an Integration of the vehicle
`lever d ata. Th ere Wlll be several such 11aps for the OSS,
`corresponding to areas in the span of coverage of the net.
`
`The final level ,s the complete or owraJJ auo m.op. In
`this example, the map Is integrated frotll the inoiv,dual area
`maps by the moni tor node.
`
`As Indicated above, the hiererchy of t asks foliow.
`directly from the de t a hierarchy. The monitor node menages
`several aua contractors. These contrectora are responsible
`tor the formation of tra tflc maps In thetr lm1111tdiate areas.
`turn, manages several pw.p
`Each area contractor,
`In
`contractors that provide It With signal groups for Its area
`( Figura 3.3). Each group contractor integrates raw signal
`d at a from stgnai contractors that heve sensing capabllltfas.
`
`The area contractors slso manage several Hine/,
`
`4 Th e
`frequency spectrum of l!Olae raaiated by a
`v ehicl e typ,c ally contains narrow b ana signal components
`that are caused by rotating machinery assocteted wtth the
`v ehicl e ( e.g .• engines or g enerators). The fr.quancies of
`such signals are correl ated with the type of rotating machine
`and
`,ts spee d of
`rotation. They are
`Indicators of
`the
`cl ass,nc;atlon ot
`the v ehicle. Narrowband signets also
`undergo shifts In
`frequency, due
`t o doppfer effect, or
`the speed of rotation of the
`instaomty and change
`In
`associated machine. Alterations rn srqnlll strength also occur
`as a result of p ropa gation conditions and venations In the
`distance between the vehicle and the sensor.
`9 A signal group that " often used to integrate nanow
`b and signal d ata. tor example, is the harmonic set, a group of
`signals th at are harmonically related (I.a .• the frequency of
`each signal ltT th e grouo is an integral multlole of the lowest.
`or fundamental freouency). A single rota ting mecn,ne often
`form a
`gives nse
`to several narrow band srgnals
`that
`harmonic set.
`
`1° For slmpllclty, we have ignored a
`the
`level in
`hierarchy that can be called compontnt swrcts of signal, as In
`level. a OSS would normally try to
`(Nii, 1978). At this
`attnbute signals and signal groups to particular pieces of
`machinery associated with a vehicle.
`
`1.5
`
`si gna l
`
`c l ass1f t cat 1on
`
`local t zation
`
`tracki ng
`
`Flgure 3.3. Area Tuk Partitioning,
`
`Note that this particular partitioning of tasks Is only one
`of many poss1bllltlas that might be specified by the system
`desrgner.
`
`3.:3 Contr act Net Implementation
`
`This section reviews In quaiitat,ve t erms ~.ow the OSS
`problem can be attacked using the contract net approach
`and illuatrates sevet'al of the Idea.a central to Its operation.
`Appendix A gives speci fic examples of the m•H81J• traffic
`th at is described here.
`
`3.3.1
`
`Initi alization
`
`The momtor node Is respensible for rnitlaliu tlon of the
`OSS and for formation of the overall map. ft must first select
`nodes to b e area contract()(S and panlhon the system's span
`of coverage ,nto areas. based on the pes1tions of those
`selected nodes. For purposes of illustration we assume that
`the monitor node knows
`the names of nodes
`that are
`potential area contract ors. but rt must eltabllsn
`their
`pos itions In order to panit1on the overall span of coverage.
`Hence. It b egins by announcing contracts for formatton of
`area maps of the traffic. Because the monitor node knows
`the names ot potenti al area contractors. rt can aVOtd a
`g eneral broadcast and c an ,nstaad use II focused addressing
`scheme. The announcement contains the three comPOnents
`d escnbed In Section 2: a task abstraction, an allg,billty
`specif ication, and a bid specification. The task abstraction Is
`simply the t ask type. and the ellgibdity spec1tlcatlon is blank
`( because the monitor node knows wn,ch other nodes are
`potential contractors and addresses them directly). The bid
`specification 1s of pnmary interest for this task. It infonns a
`prospec tive area contractor to respond with ,ts positron.
`the purpose of a brd spaertleatlon is
`to
`Remamoar tha t
`e nable a manager to se-lect, from all of the bidders. the most
`
`11 In a real solution to the OSS proolem. it 1s oossrble
`that not all of these tasks woold be large enough to Justify
`the overhead of contracting; that ls, some of them might be
`done 1n II s,ngle node. Note eiso that soma of the tasks ,n the
`h1erarcny are ,o,mnw11g t asu (e.g .• the area t ask), whtfe
`others are on,-11111, tasks (e.g., th e locahzatlon task).
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 22
`
`

`

`

`

`

`

`more complex. The question of mterast Is, U1100
`1111141
`candUian.s sltou./d a compldt signal poup dtsmptlon bt a111101Lnctd
`inJttad of a-n abstraction! The answer appears to depend on
`the qualit y of the abstrac tion. If
`the abs traction Is good
`enough
`that the vehicle contractors are able
`to make
`d efinitive statements on the bu1s of
`Its use, then the
`second approach Is likely better than the first. In that It
`minimizes local processing time. On the other hand, If the
`abstraction does not allow definitive state111ents t o be made,
`t hen ,ts use will r esult 1n increased mesnge traffic and local
`processi ng time, since the area contractor will not be certain
`as to the best course of action as a result of uncertam
`r esponses frOIII tne vehicle contractors.
`
`two
`then makes
`task
`contractor
`vehicle
`The
`v ehicle
`cl assification
`and
`vehicle
`announcements:
`localization. The t ask abstraction of the classification task
`announcement Is a list of the fundamental frequencies of the
`signal groups currently associated with the vehicle. This
`Information may help a potential class1flcatlon contractor
`s elect an appropnate teak (a contractor may, for example,
`already be familiar with v ehicles that have algnal groups with
`the announced
`fundamental
`frequencies). The ellgibllity
`s pecification 1a blank. The bid specification lndu:atH that a
`bidder should respond With a t entative claa.ification and an
`asaoclated confidence measure. This measure ia used to
`s elect a ct ass1flcatlon contractor••the bidder with
`the
`hi ghest confidenc e Is choaen. The award Is the complete
`current d escription of the vehicle.
`
`to clus1ty
`A class1flcatlon contractor may be able
`directly, given the signal group in formation: or, on the other
`h and,
`it may require more data, ,n wnich case It can
`c ommunica t e directly with the appropriate sensor nodes
`( Figure 3.8).
`
`r--- --- ·- ------ ,
`
`- ,
`
`tracki ng
`
`Fi gure 3.8. Claas1flcatlon Contract Communication.
`
`task
`locallzatlon
`a
`for
`abstraction
`t ask
`Th e
`announcement (Figure 3.9) is a list of positions of the nodes
`that h ave d et ect ed a vehicle. The ell01billty specification and
`bid specification are !)lank. The bid 1s simply an afflmatJve
`response t o the announcement and the contract ls awarded
`t o th e firs t bidder, whi ch does the required triangulation to
`ob t ain the position of the ven,cte.
`
`area
`
`r------~---- --- ,
`
`group
`
`s i gnal
`
`veh i cle
`
`- ,
`,,,,,,;,:.:.~--.~:,!.:.~~ -- tracki ng
`
`Figure 3.9. Lot:allntlon Contract lnltlatlolt,
`
`it muat be
`the vehicl e has been localized,
`Once
`t racked. This
`Is handled by the vehicle contractor by
`entering into f ollow•up localization contracts troni time to
`time and using the results to update ,t s vehicle descnption
`(Fi;ure 3 . 10). As an altemat,ve. the area contractor could
`award aepara t e tracking contracts. The decision as to which
`method to use d epends on loading and commumcatlona.
`If,
`for example,
`the area contractor
`is very busy with
`Integration of data from many group contractors. then It
`seams more appropriate to Isolate It from the additional load
`If, on
`of
`tracking contracts.
`the othllf hand,
`the area
`contractor Is not overly busy, then we can let It handle
`updated vehicle cont.rac ts, t aking advant age of the fact that
`Is In the b est pcs1tton to integrate the results and co(cid:173)
`It
`ordinate the ettorts of multiple tracking contractors. In this
`example, we asaume that the management load would be too
`large f or the area contracto,.
`
`,------·------- ,
`,------·:r~
`
`group
`
`s i gna l
`
`cla ss i f icati on
`
`l oca li zat i on
`
`tracki ng
`
`Figure 3. 1 o. Tracking Contract Ini tiation.
`
`There are a v ariety of other lasues that must be
`considered in the design and operation of a real distnbuted
`sensing sy stem. Most o f these are quite specific to the OSS
`application. and would t ake us away from our pnmary concern
`with the use of
`the contract net framewonc. One ,ssua.
`however. present s an Interesting example of the relative
`utility of th e use of contracting COll!Plfed to the use of
`information messages. Consider the case of a vehicle that Is
`moving from
`the area of one area contractor to that of
`another. How is responsibility for tracking the vehicle to be
`transferred ?
`
`There are two possibilities. First, the area contractor
`that is currently responsible for the vehicle could send out
`an information message t o ne1ghbonng area contractofs. ThlS
`message w ould serve
`to se t up expectations
`In
`the
`ne ighboring area contractora that a venicle was about to
`
`13
`
`IPR2020-00910
`Garmin, et al. EX1021 Page 25
`
`

`

`into one of t heir areas. Th e processing
`p ass
`decentralized ,n this approach.
`
`Is
`
`fully
`
`Second. t he area contractor currently res~ibl e tor
`the v e hicl e c ould send a ret)Ort to It s manager (the IIIOnltor
`node ) th at contains the same inf ormation. The moni tor node
`could then award a new contract to one of the neighboring
`a rea c ontractors to handle the vehicle when It passes out ot
`th e ong1nel area. This is a hierarchical contra, approach to
`the p roblem. It entails mo,e (centrabzed) procesu,g by the
`monitor node.
`
`With the firs t approach there i4 no guarant" that
`a noth er area contractor will pock up on the
`lnfomiation
`me s sage and immedi ately take resl)()rlSlblUty for the vehlc:le,
`w h ere t he second approach does orov1de such a guarU1tee.
`Th e l ack o f guarant ee is not generally senous, but may result
`In e x ce ss processmg because t he vehicle must be re •
`dete cted In the new area, cl assified, localized. and so on.
`The t radeott is thus one o f more ;:,rocesstng by the CQOllltor
`node a ga,~t ( possibly) mo,e processing by nodes in the new
`area. In the s,mulatlon we have used the hierarcnlcal control
`appro ach because of
`Its guarantee of
`transfer ot
`re spons1b11it y.
`
`The use o f t he c ontract net framework 1n the OSS
`enables
`Implementation of a dynamtc configuration,
`the
`d epending on t he actual positions of sensor and proces.sor
`the ease with which co111111unlcatlon can be
`nodes and
`e sta blished. Such a configuration offers a slgruflcant
`ope ra tional lmorovement over a sunk: 11 priori confl ouratton:
`spe c ifically, it ensures that nodes that must cooperate for
`the solution of t he area surveillance problem are aole to
`communic a te with aacn o ther. This al/Olds the neceuity for
`e ither Indirect routing of messag es or powerlul transmttters
`for a ll nodes.
`
`f ramework
`The distn but ed control enabled by the
`e nhan ces both reliability and equalization of t he processing
`load. It Is also posstble to recover f rom the f ailure of nodes.
`because there are explicit links between nooes that share
`respons1b1hty
`for executton of
`tasks
`(managers ano
`c ontractors). The f ailure o f a signal conm1ctor, for examol e,
`c an be detect ed by its manager. and the contract for whi<:h
`,t w a s resoonsible c an be re • announced and awaroed to
`another node.
`
`Th e framework is also advantageous fo, tllls proole11
`because 1t enabl es addition of new nodes t o the net, even
`attar operati on has commenced. This 1s pc>Mfble for two
`re asons . Firs t. the nodes communicat e 1n a conimon protocol.
`This p ro tocot enaol es I new node to Int erpret the tu k·
`independent portlon~ of messages (e.g., that a particuler
`me ssage specifies a t ask to be executed). Second. th e
`protoc ol 1s augment