Embedded Systems Handbook

Contents......Page 26
Section I: Embedded Systems......Page 30
Real-Time and Embedded Systems......Page 31
1.1 Networking of Embedded Systems......Page 32
1.2 Design Methods for Networked Embedded Systems......Page 34
1.3.1 Networked Embedded Systems in Industrial Automation......Page 36
1.3.2 Networked Embedded Systems in Building Automation......Page 38
1.3.3 Automotive Networked Embedded Systems......Page 40
1.3.4 Sensor Networks......Page 44
References......Page 45
2.1 Introduction......Page 49
2.2.1 Reference Architecture......Page 51
2.2.2 Models of Interaction......Page 52
2.2.2.3 Blackboard......Page 53
2.2.3 Execution Strategies......Page 54
2.2.4 Component-Based Design......Page 55
2.3 Real-Time Operating Systems......Page 56
2.3.2 Mechanisms for Real-Time......Page 57
2.3.3 Commercial RTOSs......Page 58
2.4.1 Introduction to Scheduling......Page 59
2.4.3.1 Priority-Based Schedulers......Page 60
2.5.1 Communication Techniques......Page 61
2.5.2.2 Time-Triggered CAN......Page 62
2.5.2.7 ARINC 629......Page 63
2.5.3.2 Usage of Tokens......Page 64
2.5.4 Wireless Communication......Page 65
2.6.1.2 Response Time......Page 66
2.6.1.4 Jitter......Page 67
2.6.2.2 Schedulability Analysis......Page 68
2.6.3.1 Analysis of Tasks......Page 69
2.6.3.2 Analysis of Messages......Page 71
2.6.4 Trends and Tools......Page 72
2.7.1.1 Execution Time......Page 73
2.7.1.2 Response Time......Page 74
2.7.1.5 Summary of Timing and CBD......Page 75
2.7.2.2 RTOSs that Support CBD......Page 76
2.8 Testing and Debugging of RTSs......Page 77
2.9 Summary......Page 78
References......Page 79
Design and Validation of Embedded Systems......Page 84
3.1 The Embedded System Revolution......Page 85
3.2 Design of Embedded Systems......Page 86
3.3 Functional Design......Page 90
3.4 Function–Architecture and Hardware–Software Codesign......Page 91
3.5 Hardware–Software Coverification and Hardware Simulation......Page 95
3.6.1 Compilation, Debugging, and Memory Model......Page 96
3.6.2 Real-Time Scheduling......Page 98
3.7.1 Logic Synthesis and Equivalence Checking......Page 100
3.7.2 Placement, Routing, and Extraction......Page 102
3.7.3 Simulation, Formal Verification, and Test Pattern Generation......Page 103
References......Page 106
4.1 Introduction......Page 109
4.1.1 Models of Sequential and Parallel Computation......Page 110
4.1.2 Nonfunctional Properties......Page 111
4.1.3 Heterogeneity......Page 113
4.1.5 Time......Page 114
4.1.6 The Purpose of an MoC......Page 116
4.2 The MoC Framework......Page 117
4.2.1 Processes and Signals......Page 118
4.2.3.1 Process Constructors......Page 119
4.2.3.2 Composition Operators......Page 120
4.2.4.1 Process Constructors......Page 121
4.2.4.3 The Clocked Synchronous MoC......Page 122
4.2.5 Discrete Timed MoCs......Page 123
4.3.1 MoC Interfaces......Page 124
4.3.2 Interface Refinement......Page 126
4.3.3 MoC Refinement......Page 128
4.4 Conclusion......Page 130
References......Page 131
5.1 Introduction......Page 134
5.2 Notions of Time......Page 136
5.3 Communication Support......Page 137
5.4.1 Finite State Machines......Page 138
5.4.3 Statecharts and Hierarchical/Concurrent Finite State Machines......Page 141
5.4.4 Program-State Machines......Page 145
5.4.5 Codesign Finite State Machines......Page 147
5.4.6 Specification and Description Language......Page 148
5.4.7 Message Sequence Charts......Page 152
5.4.8 Petri Nets......Page 156
5.4.9 Discrete Event......Page 159
5.4.10 Synchronous/Reactive Models......Page 160
5.4.11 Dataflow Models......Page 162
5.5 Conclusions......Page 164
References......Page 165
6.1 Introduction......Page 168
6.2 Mathematical Models of Embedded Systems......Page 169
6.2.1 Transition Systems......Page 170
6.2.2.1 Behaviors......Page 171
6.2.2.2 Bisimilarity......Page 172
6.2.2.3.1 Parallel Composition of Behaviors......Page 174
6.2.3 Environments......Page 175
6.2.3.1 Insertion Functions......Page 177
6.2.3.2.1 Local and Shared Store......Page 179
6.2.3.2.2 Multilevel Store......Page 180
6.2.3.2.3 Message Passing......Page 181
6.2.4.1 Process Algebras......Page 182
6.2.4.2 Temporal Logic......Page 183
6.2.4.3 Timed Automata......Page 184
6.2.4.5 Rewriting Logic......Page 185
6.3 Requirements Capture and Validation......Page 186
6.3.1 Approaches to Requirements Validation......Page 187
6.3.2 Tools for Requirements Validation......Page 188
6.3.2.1.1 Vienna Development Method......Page 189
6.3.2.1.4 Rigorous Approach to Industrial Software Engineering......Page 190
6.3.2.1.7 EVES......Page 191
6.3.2.2.3 PVS......Page 192
6.3.2.2.6 Nuprl......Page 193
6.3.2.3.2 Spin......Page 194
6.3.2.3.5 CADP......Page 195
6.4 Specifying and Verifying Embedded Systems......Page 196
6.4.2 Static Requirements......Page 197
6.4.4 Example: Railroad Crossing Problem......Page 198
6.4.5 Requirement Specifications......Page 200
6.4.5.3 Requirements for Synchronous Agents......Page 202
6.4.6.1 Algebraic Programming......Page 204
6.4.6.2 Simulating of Transition Systems......Page 205
6.4.7 Consistency and Completeness......Page 206
6.5 Examples and Results......Page 207
6.5.1 Example: Embedded Operating System......Page 209
6.5.1.1.1 Requirements for new_task......Page 210
6.5.1.1.4 Requirements for Schedule......Page 211
6.5.1.1.5 Interrupts......Page 212
6.5.1.2 Input Text to the Consistency Checker......Page 213
6.5.2.1 OSEK......Page 215
6.5.2.3 V’ger......Page 216
References......Page 217
Design and Verification Languages......Page 225
7.1 Introduction......Page 226
7.2.1 Assembly Languages......Page 227
7.2.2 The C Language......Page 229
7.2.3 C++......Page 230
7.2.5 Real-Time Operating Systems......Page 231
7.3 Hardware Languages......Page 233
7.3.1 Verilog......Page 234
7.3.2 VHDL......Page 236
7.4 Dataflow Languages......Page 237
7.4.1 Kahn Process Networks......Page 238
7.5 Hybrid Languages......Page 239
7.5.2 SDL......Page 240
7.5.3 SystemC......Page 242
References......Page 243
8.1 Introduction......Page 245
8.2.1 What For?......Page 246
8.2.2 Basic Notions......Page 247
8.2.3 Mathematical Models......Page 248
8.3 Imperative Style: Esterel and SyncCharts......Page 249
8.3.1 Syntax and Structure......Page 250
8.3.3 Compilation and Compilers......Page 252
8.3.4 Analysis/Verification/Test Generation: Benefits from Formal Approaches......Page 254
8.4.1 A Synchronous Model of Computation......Page 255
8.4.2 Declarative Design Languages......Page 256
8.4.2.1 Combinators for Lustre......Page 257
8.4.2.2 Combinators for Signal......Page 258
8.4.3.1.2 Hierarchization......Page 259
8.4.3.3 Certification......Page 261
8.6 Into the Future: Perspectives and Extensions......Page 262
8.6.1 Asynchronous Implementation of Synchronous Specifications......Page 263
References......Page 264
9.1 Introduction......Page 268
9.2.1 Static System Structure......Page 269
9.2.2 System Behavior......Page 270
9.2.4 Embedded Systems and UML......Page 272
9.3.1 Domain Statement and Domain Model......Page 274
9.3.2 Behavior Overview through a Use Case Diagram......Page 275
9.3.4 Behavior Modeling with Interactions......Page 276
9.3.4.1 A Simple Sequence Diagram for a Simple Situation......Page 277
9.3.4.2 Factoring out General/Common Interactions......Page 279
9.3.4.3 Describing the Full Withdrawal Service......Page 280
9.3.5 Behavioral Modeling with State Machines......Page 281
9.3.5.2 High-Level ATM with Submachine States......Page 282
9.3.5.4 Flexibility through Specialization......Page 284
9.3.6 Validation......Page 288
9.3.7.2 Generalizing with State Machines......Page 289
9.3.8 Hierarchical Decomposition......Page 290
9.3.8.2 Decomposition of Lifelines......Page 291
9.3.9 The Difference between the UML System and the Final System......Page 292
9.3.9.2 Errors and Noise......Page 293
9.3.9.3 Physical Distribution......Page 294
9.3.9.5 Concurrency and Independence......Page 296
9.4 A UML Profile for the Modeling of Embedded Systems......Page 297
References......Page 299
10.1 Introduction......Page 301
10.2.1 Simulation-Based Verification......Page 302
10.2.2 Formal Verification......Page 303
10.2.4 Formal Specification of Properties......Page 304
10.2.4.3 Temporal Logics......Page 305
10.3.1 HDLs and Interfaces to Programming Languages......Page 306
10.3.3 Temporal e......Page 307
10.3.6 Property Specification Language......Page 309
10.4.1.2 Verification of Java Programs......Page 311
10.4.2 Software Modeling Languages......Page 312
10.5.1.2 SpecC......Page 313
10.5.1.3 SystemVerilog and SystemVerilog Assertions......Page 314
10.5.2.1 Synchronous Languages......Page 315
10.5.2.2 Languages for Hybrid Systems......Page 316
References......Page 317
Operating Systems and Quasi-Static Scheduling......Page 321
11.1 Introduction......Page 322
11.2.1 Overall System Architecture......Page 324
11.2.3 Processor Scheduling......Page 326
11.2.4 Interprocess Synchronization and Communication......Page 327
11.2.6 Additional Functions......Page 329
11.3.1 Attribute Objects......Page 330
11.3.2 Multithreading......Page 332
11.3.3 Process and Thread Scheduling......Page 333
11.3.4 Real-Time Signals and Asynchronous Events......Page 335
11.3.4.1 Generation of a Signal......Page 336
11.3.4.3 Signal Delivery and Acceptance......Page 337
11.3.5.1 Message Queues......Page 338
11.3.5.3 Mutexes......Page 339
11.3.5.5 Shared Memory......Page 340
11.3.6 Thread-Specific Data......Page 341
11.3.8 Asynchronous and List Directed Input and Output......Page 342
11.3.9 Clocks and Timers......Page 343
11.4 Real-Time, Open-Source Operating Systems......Page 344
11.5.2 Views of Processor State......Page 346
11.5.3 Operating Principle......Page 347
11.5.4 Virtualization by Instruction Emulation......Page 348
11.5.5 Processor-Mode Change......Page 349
11.5.6 Privileged Instruction Emulation......Page 350
11.5.8 Interrupt Handling......Page 351
11.5.9 Trap Redirection......Page 352
11.5.10 VMM Processor Scheduler......Page 353
References......Page 354
12.1 Introduction......Page 356
12.2 Periodic Task Handling......Page 357
12.2.1 Timeline Scheduling......Page 358
12.2.2 Rate Monotonic Scheduling......Page 359
12.2.4 Tasks with Deadlines Less than Periods......Page 360
12.3 Aperiodic Task Handling......Page 361
12.4.1 Priority Inheritance Protocol......Page 364
12.4.2 Priority Ceiling Protocol......Page 365
12.5 New Applications and Trends......Page 366
References......Page 367
13.1.1 Quasi-Static Scheduling......Page 369
13.1.2 A Simple Example......Page 370
13.2 Overview of Related Work......Page 372
13.3.1 Definitions......Page 373
13.3.2 Specification Model......Page 374
13.3.3 Schedulability Analysis......Page 375
13.3.4 Algorithmic Implementation......Page 377
13.4.1 Definitions......Page 378
13.4.2.1 Bounded Length Schedules......Page 379
13.4.3 Comparison to PN Model......Page 380
References......Page 382
Timing and Performance Analysis......Page 384
14: Determining Bounds on Execution Times......Page 385
14.1 Introduction......Page 386
14.1.1 Tool Architecture and Algorithm......Page 387
14.1.2 Timing Anomalies......Page 388
14.1.3 Contexts......Page 389
14.2.2 Cache Semantics......Page 390
14.2.2.1 Control Flow Representation......Page 391
14.2.3 Abstract Semantics......Page 392
14.2.3.2 Must Analysis......Page 393
14.3 Pipeline Analysis......Page 394
14.3.1 Simple Architectures without Timing Anomalies......Page 395
14.3.2 Processors with Timing Anomalies......Page 396
14.3.3 Algorithm Pipeline-Analysis......Page 397
14.3.4.1 The ColdFire MCF 5307 Pipeline......Page 398
14.3.5 Formal Models of Abstract Pipelines......Page 399
14.4 Path Analysis Using Integer Linear Programming......Page 401
14.5.2 Control Flow Specification and Analysis......Page 402
14.6.2.1 The Timing-Schema Approach......Page 403
14.7 State of the Art and Future Extensions......Page 404
References......Page 405
15.1.1 Distributed Embedded Systems......Page 408
15.1.2 Basic Terms......Page 410
15.1.3 Role in the Design Process......Page 411
15.1.4 Requirements......Page 412
15.2.1 Simulation-Based Methods......Page 413
15.2.2 Holistic Scheduling Analysis......Page 415
15.2.3 Compositional Methods......Page 416
15.3.1 Performance Network......Page 418
15.3.2 Variability Characterization......Page 419
15.3.3 Resource Sharing and Analysis......Page 421
15.3.4 Concluding Remarks......Page 423
References......Page 424
Power Aware Computing......Page 426
16.1 Introduction......Page 427
16.2 Energy and Power Modeling......Page 429
16.2.1 Instruction- and Function-Level Models......Page 430
16.2.2 Micro-Architectural Models......Page 431
16.2.4 Battery Models......Page 432
16.3 System/Application Level Optimizations......Page 433
16.4.1 Voltage and Frequency Scaling......Page 434
16.4.2 Dynamic Resource Scaling......Page 435
16.4.3 Processor Core Selection......Page 436
16.5.1 Cache Hierarchy Tuning......Page 437
16.5.3 Dynamic Scaling of Memory Elements......Page 439
16.5.4 Software-Controlled Memories, Scratch-Pad Memories......Page 440
16.5.6 Special Purpose Memory Subsystems for Media Streaming......Page 441
16.5.8 Interconnect Optimizations......Page 442
References......Page 443
Security in Embedded Systems......Page 451
17.1 Introduction......Page 452
17.2 Security Parameters......Page 453
17.2.2 Security Implementation Levels......Page 454
17.3.1 Energy Considerations......Page 455
17.3.2 Processing Power Limitations......Page 456
17.3.4 Cost of Implementation......Page 457
17.4.1 System Design Issues......Page 458
17.4.2 Application Design Issues......Page 460
17.5 Cryptography and Embedded Systems......Page 461
17.5.1 Physical Security......Page 462
17.5.2 Side-Channel Cryptanalysis......Page 463
17.5.3.1 Fault-Induction Techniques......Page 464
17.5.3.2 Passive Side Channels......Page 465
17.5.4 Fault-Based Cryptanalysis......Page 466
17.5.4.1 Case Study: RSA–Chinese Remainder Theorem......Page 467
17.5.5 Passive Side-Channel Cryptanalysis......Page 468
17.5.6 Countermeasures......Page 469
References......Page 471
Section II: System-on-Chip Design......Page 478
18.1 Introduction......Page 479
18.3 System-on-a-Programmable-Chip......Page 480
18.4 IP Cores......Page 482
18.6 Platforms and Programmable Platforms......Page 483
18.7 Integration Platforms and SoC Design......Page 484
18.8 Overview of the SoC Design Process......Page 485
18.9 System-Level Design......Page 488
18.11 Computation and Memory Architectures for SoC......Page 489
18.13 Summary......Page 490
References......Page 491
19.1 Introduction......Page 493
19.2 Related Work......Page 495
19.3.1 Architecture Exploration......Page 496
19.3.2 LISA Language......Page 497
19.4.1 Hardware Designer Platform — For Exploration and Processor Generation......Page 502
19.4.3 System Integrator Platform — For System Integration and Verification......Page 503
19.5.2 Simulator......Page 504
19.5.2.1 Compiled Simulation......Page 505
19.5.2.3 Static Scheduling......Page 506
19.5.2.3.1 Operation Instantiation......Page 507
19.5.2.3.2 Simulator Instantiation......Page 508
19.6 Architecture Implementation......Page 509
19.6.1.1 The Resource Section......Page 510
19.6.2 Implementation Results......Page 511
19.6.2.2 Gate Level Synthesis......Page 512
19.6.2.2.4 Power Consumption Comparison......Page 513
19.7.1 Examined Architectures......Page 514
19.7.2.1 Performance of the Simulator......Page 515
19.8.3 HDL Generator......Page 517
References......Page 518
20.1 Introduction......Page 521
20.2.1 AMBA System Bus......Page 522
20.2.3 Advanced Peripheral Bus......Page 524
20.2.4.2 AMBA AXI Protocol......Page 525
20.3 CoreConnect Bus......Page 527
20.3.1 Processor Local Bus......Page 528
20.3.3 Device Control Register Bus......Page 529
20.4 STBus......Page 530
20.5 Wishbone......Page 531
20.6 SiliconBackplane MicroNetwork......Page 532
20.6.2 Configuration Resources......Page 533
20.7.2 Avalon......Page 534
20.8 Analysis of Communication Architectures......Page 535
20.8.1 Scalability Analysis......Page 537
20.9 Packet-Switched Interconnection Networks......Page 540
References......Page 541
21.1 Introduction......Page 543
21.2 Design Challenges for On-Chip Communication Architectures......Page 545
21.3 Related Work......Page 546
21.4.1 Network Link......Page 547
21.4.2 Switch......Page 549
21.4.3 Network Interface......Page 552
21.5 NoC Topology......Page 555
21.5.1 Domain-Specific NoC Synthesis Flow......Page 556
21.6 Conclusions......Page 558
References......Page 559
22.1 Introduction......Page 562
22.2 Platform-Based Design......Page 564
22.3.1 (Micro-)Architecture Platforms......Page 565
22.3.2 API Platform......Page 566
22.3.3 System Platform Stack......Page 567
22.4.1 Definitions......Page 568
22.4.2 Quality of Service......Page 569
22.5.1 Types of Faults and Platform Redundancy......Page 570
22.5.2 Fault-Tolerant Design Methodology......Page 571
22.5.2.3 Example......Page 572
22.5.2.4 Platform Characteristics......Page 573
22.5.2.5 Design Flow......Page 574
22.5.3.2.2 Memory Actors (State Memories)......Page 575
22.6 Analog Platforms......Page 576
22.6.1 Definitions......Page 577
22.6.2.1 Performance Model Approximation......Page 579
22.6.2.2 Optimizing the Approximation Process......Page 580
22.6.3 Mixed-Signal Design Flow with Platforms......Page 581
22.7 Concluding Remarks......Page 583
References......Page 585
23.1 Introduction......Page 588
23.2 Related Work......Page 589
23.3.1 Interface Specification......Page 591
23.3.2 Requirements Specification......Page 592
23.3.3 Synthesis......Page 593
23.4 Algebraic Formulation......Page 597
23.4.1 Trace-Based Solution......Page 599
23.4.2 End-to-End Specification......Page 601
23.5 Conclusions......Page 605
References......Page 606
24.1 Introduction......Page 608
24.2.1 System-Level Design Flow......Page 610
24.2.2 SoC Design Automation — An Overview......Page 611
24.3.1 Introduction to IP Integration......Page 612
24.3.2 Bus-Based and Core-Based Approaches......Page 613
24.3.4 Communication Synthesis......Page 614
24.4 Component-Based SoC Design......Page 615
24.4.1 Design Methodology Principles......Page 616
24.4.4 HW/SW Wrapper Architecture......Page 617
24.4.5 Design Tools......Page 618
24.4.6 Defining IP-Component Interfaces......Page 620
24.5.1 Specification......Page 621
24.5.2 DFU Abstract Architecture......Page 622
24.5.3 MPSoC RTL Architecture......Page 623
24.5.4 Results......Page 624
24.5.5 Evaluation......Page 625
References......Page 626
25.1 Introduction......Page 628
25.2 Related Work......Page 629
25.3 TTL Interface Requirements......Page 630
25.4.1 Inter-Task Communication......Page 631
25.4.1.2 Interface Type CB......Page 632
25.4.1.3 Interface Types RB and RN......Page 633
25.4.2 TTL Multi-Tasking Interface......Page 634
25.5.1.1 Optimization for Single Interface Types......Page 635
25.5.1.2 Optimization across Interface Types......Page 636
25.5.1.4 Channel and Task Merging and Splitting......Page 638
25.5.2.1 Parser Generation......Page 639
25.5.2.3 Automatic Interface Type Refinement......Page 640
25.6.1 The Multi-DSP Architecture......Page 641
25.6.2.1 Channel Administration......Page 642
25.6.3.1 Evaluation Application......Page 643
25.6.4 Implementation Conclusions......Page 644
25.7.1 The Smart Imaging Core......Page 645
25.7.2.1 TTL Shell for the SI Coprocessor......Page 646
25.8 Conclusions......Page 648
References......Page 649
26: A Multiprocessor SoC Platform and Tools for Communications Applications......Page 651
26.2 Wire-Speed Packet Forwarding Challenges......Page 652
26.2.2 Survey of Multiprocessor SoC Platforms......Page 653
26.3 Platform and Development Environment Overview......Page 654
26.4 StepNP Architecture Platform......Page 655
26.4.2 Network-on-Chip......Page 656
26.4.4 Configurable Processor Implementation......Page 658
26.5 Multiflex MP-SoC Tools Overview......Page 659
26.6.1 Modeling Language......Page 660
26.6.3 SOCP Network-on-Chip Channel Interface......Page 661
26.7 Multiflex Model Control-and-View Support Framework......Page 662
26.7.2 SIDL Interface......Page 663
26.8.1 Survey of Multiprocessor Programming Models......Page 664
26.8.2 Multiflex Programming Model Overview......Page 665
26.9 DSOC Programming Model......Page 666
26.9.2 The DSOC ORB......Page 667
26.10.1 Target SMP Platform......Page 669
26.11.1 Networking Application Framework......Page 671
26.11.2 StepNP Target Architecture......Page 672
26.11.4 Multiprocessor Compilation and Distribution......Page 673
26.11.5 IPv4 Results......Page 674
26.12 A Traffic Manager Application......Page 675
26.12.2 DSOC Model......Page 676
26.12.3 StepNP Target Architecture......Page 677
26.12.4 DSOC + SMP Model......Page 678
26.13 Summary......Page 679
26.14 Outlook......Page 680
References......Page 681
Section III: Testing of Embedded Core-Based Integrated Circuits......Page 684
27.1 Introduction......Page 685
27.1.2 Testing an SOC......Page 687
27.1.3 Built-In Self-Test......Page 688
27.2 Modular Testing of SOCs......Page 689
27.2.1 Wrapper Design and Optimization......Page 690
27.2.2 TAM Design and Optimization......Page 691
27.2.3 Test Scheduling......Page 693
27.2.4 Integrated TAM Optimization and Test Scheduling......Page 694
27.2.5 Modular Testing of Mixed-Signal SOCs......Page 695
27.2.5.1 Analog Test Wrapper Modes......Page 697
27.3 BIST Using a Reconfigurable Interconnection Network......Page 698
27.3.1 Declustering the Care Bits......Page 701
27.4 Conclusions......Page 706
References......Page 707
28: Embedded Software-Based Self-Testing for SoC Design......Page 712
28.1 Introduction......Page 713
28.2 Embedded Processor Self-Testing......Page 715
28.2.1.1 Test Preparation......Page 716
28.3 Test Program Synthesis Using VCCs......Page 717
28.4 DelayTesting......Page 721
28.6 Self-Testing of Buses and Global Interconnects......Page 722
28.7 Self-Testing of Other Nonprogrammable IP Cores......Page 725
28.8 Instruction-Level DfT/Test Instructions......Page 726
28.9 Self-Test of On-Chip ADC/DAC and Analog Components Using DSP-Based Approaches......Page 727
Acknowledgments......Page 728
References......Page 729
Section IV: Networked Embedded Systems......Page 731
29.1 Introduction......Page 732
29.2.1 Functionality and Constraints......Page 733
29.2.3 Usability, Dependability, and Availability......Page 734
29.3.1 Automobile: Safety-Critical Versus Telematics......Page 736
29.3.2 Data Acquisition: Precision Agriculture and Habitat Monitoring......Page 737
29.3.3 Defense Applications: Battle-Space Surveillance......Page 738
29.4 Design Considerations for NES......Page 739
29.5.1 Hardware......Page 741
29.5.2 Software......Page 742
29.6 Design Methodologies and Tools......Page 744
29.7 Conclusions......Page 746
References......Page 747
30.1 Introduction......Page 750
30.1.2 Networked Embedded Systems Middleware......Page 751
30.1.3 Example Application: Ping-Node Scheduling for Active Damage Detection......Page 752
30.1.5 Middleware Design and Implementation Challenges......Page 753
30.2 Middleware Solution Space......Page 754
30.3 ORB Middleware for Networked Embedded Systems — A Case Study......Page 756
30.3.2 Object Adapter......Page 757
30.3.5 Priority Propagation......Page 758
30.3.6 Simulation Support......Page 759
30.4 Design Recommendations and Trade-Offs......Page 761
30.6 Concluding Remarks......Page 762
References......Page 763
Section V: Sensor Networks......Page 767
31.1 The Third Era of Computing......Page 768
31.2 What Are Wireless Sensor Networks?......Page 769
31.3 Typical Scenarios and Applications......Page 770
31.4 Design Challenges......Page 772
31.4.1 Locally Available Resources......Page 773
31.4.3 Needed Algorithms......Page 774
31.4.4 Dependability......Page 775
References......Page 776
32.1 Introduction......Page 778
32.1.1 Sensor Networks versus Mobile ad hoc Networks......Page 779
32.2.1 Operational Model......Page 780
32.3 Design Issues in Sensor Networks......Page 781
32.5 Routing......Page 782
32.5.2 Cluster-Based Routing Protocols......Page 783
32.6.1.2 Proposed Security Protocols......Page 784
32.6.2 Location Determination......Page 785
32.6.4 Power Management......Page 786
32.6.5 Clock Synchronization......Page 787
32.6.7 Sensor Placement and Organization for Coverage and Connectivity......Page 788
32.6.7.2 Sensor Organization for Connectivity and Coverage......Page 789
32.7 Conclusions......Page 790
References......Page 791
33: Architectures for Wireless Sensor Networks......Page 795
33.1 Sensor Node Architecture......Page 796
33.1.1 Mathematical Energy Consumption Model of a Node......Page 798
33.2.1 Protocol Stack Approach......Page 799
33.2.2 EYES Project Approach......Page 802
33.2.2.1 Distributed Services Layer Examples......Page 804
33.2.2.1.1 Directed Diffusion......Page 805
33.2.2.1.3 TinyDB......Page 806
33.2.2.1.4 Discussion......Page 808
33.3.1 Motivation......Page 811
33.3.2 Architecture Description......Page 812
33.3.2.1 Requirements......Page 813
References......Page 815
34.1 Introduction......Page 817
34.1.1.2 Carrier Sense Multiple Access with Collision Avoidance......Page 818
34.1.2.1 Time-Division Multiple Access......Page 820
34.2.1 Hardware Characteristics......Page 821
34.2.2 Communication Patterns......Page 822
34.3.1 Sources of Overhead......Page 823
34.3.2 Trade-Offs......Page 824
34.3.2.1 Use Multiple Channels, or Not?......Page 825
34.3.2.3 Get Notified, or Not?......Page 826
34.4.2 LPL and Preamble Sampling......Page 827
34.5 Slotted Protocols......Page 828
34.5.2 Timeout-MAC......Page 829
34.6 TDMA-Based Protocols......Page 830
34.6.1 Lightweight Medium Access......Page 832
34.7.1 Simulation Framework......Page 833
34.7.2 Micro-Benchmarks......Page 835
34.7.3 Homogeneous Unicast and Broadcast......Page 837
34.7.5 Convergecast......Page 840
34.7.6 Discussion......Page 841
Acknowledgments......Page 843
References......Page 844
35.1 Introduction......Page 846
35.2 Design Challenges......Page 847
35.4 Basics of Time Synchronization......Page 848
35.5 Time Synchronization Protocols for Sensor Networks......Page 851
References......Page 854
36.1 Introduction......Page 856
36.2 Localization Algorithms......Page 857
36.2.1 Generic Approach......Page 858
36.2.2 Phase 1: Distance to Anchors......Page 859
36.2.2.3 Euclidean......Page 860
36.2.3.1 Lateration......Page 861
36.2.3.2 Min-Max......Page 862
36.3 Simulation Environment......Page 863
36.4 Results......Page 864
36.4.1.3 Euclidean......Page 865
36.4.2.1 Distance Errors......Page 867
36.5.1 Phases 1 and 2 Combined......Page 869
36.5.1.2 Accuracy......Page 870
36.5.2 Phase 3: Refinement......Page 871
36.5.3 Communication Cost......Page 873
36.5.4 Recommendations......Page 874
36.6 Conclusions......Page 876
References......Page 877
37.1 Introduction......Page 879
37.2.1.3 Minimum Cost Forwarding Algorithm for Large Sensor Networks......Page 880
37.2.1.4 Flow-Based Routing Protocol......Page 881
37.2.1.6 Geographic Routing Protocols......Page 882
37.2.2.1 Low-Energy Adaptive Clustering Hierarchy......Page 883
37.2.2.2 Threshold Sensitive Energy-Efficient Sensor Network Protocol......Page 884
References......Page 885
38.1 Introduction......Page 887
38.2.1 Background......Page 889
38.2.2 Mathematical Formulation of the Problem......Page 890
38.3.1 Ill-Posed Linear Operator Equations......Page 892
38.3.2 Regularization Methods for Solving Ill-Posed Linear Operator Equations......Page 893
38.3.2.1 Tikhonov’s Method......Page 894
38.4 Spectrum Estimation Using Generalized Projections......Page 895
38.5.1 The Ring Algorithm......Page 897
38.5.2 The Star Algorithm......Page 898
References......Page 903
39: Sensor Network Security......Page 905
39.1 Introduction and Motivation......Page 906
39.2 DoS and Routing Security......Page 908
39.3 Energy Efficient Confidentiality and Integrity......Page 911
39.4 Authenticated Broadcast......Page 915
39.5 Alternative Approaches to Key Management......Page 917
39.6 Secure Data Aggregation......Page 923
39.7 Summary......Page 925
References......Page 926
40.1 Introduction......Page 928
40.2 Preliminaries......Page 929
40.2.1 Architectural Layer Model......Page 930
40.2.3 Programming Aspect versus Behavioral Aspect......Page 931
40.3.1.1 Elemental Properties......Page 932
40.3.1.2 TinyOS Design......Page 933
40.3.2 MATÉ......Page 934
40.3.2.1 MATÉ Architecture......Page 935
40.3.3 TinyDB......Page 936
40.3.4.1 Basic Architecture and Concepts......Page 937
40.3.6 EnviroTrack......Page 939
40.3.7.1 SeNeTs Architecture......Page 940
40.3.7.2 Interface Optimization......Page 941
40.4 Simulation, Emulation, and Test of Large-Scale Sensor Networks......Page 943
40.4.1 TOSSIM — A TinyOS SIMulator......Page 944
40.4.2 EmStar......Page 945
40.4.2.1 EmStar Tools and Services......Page 946
40.4.3.1 System Architecture......Page 948
40.4.3.4 SeNeTs Application......Page 949
40.4.3.5 Environment Management......Page 950
References......Page 952
Section VI: Embedded Applications......Page 954
Automotive Networks......Page 955
41.1.1 Economic and Social Context......Page 956
41.1.2.1 Power Train......Page 957
41.1.2.3 Body......Page 958
41.1.3.1.1 Controller Area Network......Page 959
41.1.3.1.3 J1850......Page 960
41.1.3.1.7 Media Oriented System Transport......Page 961
41.1.3.2 Operating Systems......Page 962
41.2.1 Architecture Description Languages......Page 963
41.2.2 EAST-ADL for In-Vehicle Embedded System Modeling......Page 964
41.3.1 General View of Validation Techniques......Page 965
41.3.2 Validation by Performance Evaluation......Page 966
41.3.2.1.3 Operational Level......Page 967
41.3.2.1.4 Performance Properties......Page 970
41.3.2.2.1 Configuration 1......Page 971
41.3.2.2.4 Configuration 4......Page 972
41.3.2.3.2 Worst-Case Evaluation......Page 973
41.3.2.5 Automatic Generation of Models for Simulation Purpose......Page 974
41.4 Conclusions and Future Trends......Page 975
41.5 Appendix: In-Vehicle Electronic System Development Projects......Page 976
References......Page 977
42.1 Introduction......Page 979
42.1.1 The Issue of Safety-Critical Systems in the Automotive Industry......Page 980
42.2 Safety-Relevant Communication Services......Page 981
42.2.1.2 Time-Triggered Transmissions......Page 982
42.2.1.4 Atomic Broadcast and Acknowledgment......Page 983
42.2.2.1 Group Membership Service......Page 984
42.2.2.2.1 Fail-Silence Property......Page 985
42.3 Fault-Tolerant Communication Systems......Page 986
42.3.2 Scalable Dependability: FlexRay......Page 987
42.3.3 Adding Missing Features to an Existing Protocol: CAN......Page 988
42.3.3.2 Improving Error Confinement......Page 989
References......Page 990
43.1 Introduction......Page 994
43.2 Volcano Concepts......Page 996
43.2.1 Volcano Signals and the Publish/Subscribe Model......Page 997
43.2.2 Frames......Page 998
43.2.4.1 Volcano Thread-of-Control......Page 999
43.2.5 Timing Model......Page 1000
43.2.5.1 Jitter......Page 1001
43.2.6 Capture of Timing Constraints......Page 1002
43.3.1 The Car OEM Tool Chain — One Example......Page 1003
43.3.2.1 Global Objects......Page 1004
43.3.2.3 Database......Page 1005
43.3.2.7 Volcano Filtering Algorithm......Page 1006
43.3.2.8 Multiprotocol Support......Page 1007
43.4.1.1 The Configuration Files......Page 1008
43.4.2 Workflow......Page 1009
More Information......Page 1011
Industrial Automation......Page 1012
44.1 Objective and Contents......Page 1013
44.2 Application Context......Page 1014
44.3.1 Embedded Server Functions......Page 1016
44.3.2 Embedded Site Structure......Page 1017
44.3.3 Embedded Server Operation......Page 1018
44.3.3.1 Minimal Server Interface......Page 1019
44.3.3.3 Operation Phase......Page 1020
44.4.1 Steps of Embedded Site Implementation Process......Page 1022
44.4.2 Implementation of VFS......Page 1023
44.4.3 Implementation of Look-and-Feel Objects......Page 1025
44.4.4 Implementation of Page Composition Routines......Page 1026
44.4.4.1 Template-Based Dynamic Pages......Page 1027
44.4.6 Implementation of Application Wrappers......Page 1029
44.4.7 Putting Pieces Together......Page 1030
44.5 Example of Site Implementation in a HART Protocol Gateway......Page 1032
44.5.1 Structure of the Site Embedded in the Protocol Gateway......Page 1033
44.5.3 Access to Site — Home Page......Page 1035
44.5.4 Access to Parameters of the Gateway......Page 1036
44.5.6 Access to Channel Parameters......Page 1037
44.5.8 Access Control and Authentication......Page 1039
44.5.9 Application Wrapper......Page 1041
44.6.1 Embedded Site Architecture......Page 1043
44.6.1.2 Directory di80_params......Page 1044
44.6.1.4 Directory _fpclass......Page 1046
44.6.2.1 Test Platform......Page 1047
44.6.3.3 Authentication......Page 1048
44.6.3.7 Access to Channel Parameters......Page 1049
References......Page 1050
44.A1.1 Programming of VFS Component......Page 1051
44.A1.1.1 Specification Structure......Page 1052
44.A1.3 Specification Example......Page 1053
45.1.1 Motivation......Page 1056
45.1.3 Outline......Page 1057
45.2.2 IPSec......Page 1058
45.3 Basic Access Authentication Scheme......Page 1059
45.4.1 Cryptographical Prerequisites......Page 1060
45.4.2 Digest Authentication......Page 1061
45.4.3 Digest Authentication with Integrity Protection......Page 1062
45.4.5 Summary......Page 1063
45.5.2 Replay Attacks......Page 1064
45.5.6 URI Check......Page 1065
45.6.2 Browsers......Page 1066
Appendix: A Brief Review of the HTTP......Page 1067
References......Page 1069
Intelligent Sensors......Page 1070
46.1 Introduction......Page 1071
46.2.1 Analysis......Page 1072
46.2.2 The External Model......Page 1074
46.2.3 Functional Decomposition of a Service......Page 1076
46.2.4 Sensor Architectural Design......Page 1078
46.3.1 Description......Page 1080
46.3.2 Illustration......Page 1082
46.3.3 Implementation......Page 1084
46.4 Conclusion......Page 1087
References......Page 1088