Transcript 18-525 Architecture Proposal Giovanni Fonseca David Fu Amir Ghiti

RF Triangulator: Indoor/Outdoor
Location Finding
18-525 Architecture Proposal
Giovanni Fonseca
David Fu
Amir Ghiti
Stephen Roos
Design Manager: Myron Kwai
Overall Project Objective:
Design a Radio-Frequency indoor/outdoor navigation
system, utilizing the existing wireless infrastructure.
Design Stage Objective:
Implement functional (behavioral) Verilog description
New Design Proposal
► Using
existing 802.11 wireless signals it is
possible to calculate one’s location without
the use of GPS.
► The RF Triangulator will use current
infrastructures to act as an indoor/outdoor
local positioning system
► By acquiring signal data from 3 or more
wireless access points it will be possible to
determine one’s coordinates to within
1 meter.
Triangulation Process
► Our
chip will
solve for the
simultaneous
solution of 3
circle
equations.
RF Triangulator Applications:
► Our
chip can be integrated into handheld
computers, watches, or shopping carts for
locations ranging from large theme parks to
office buildings.
► It will be able to quickly provide your
current location as well as provide a
distance and heading to a future location for
path-finding purposes.
Current Project Status:
► Finish
debugging the behavioral description
of the RF Triangulator chip
► Starting preparations for structural Verilog
► Deciding how many arithmetic units we need
and comparing performance vs. size
► Optimizing main algorithms
► Deciding on timing/pipelining implementation
Design Decisions:
► We
conceived a completely new and better
design than the RF-ID credit card.
► We decided that the RF-ID credit card was
mostly encryption based and lacked
originality
► The 16-bit floating point precision is
sufficiently precise for our application.
Design Decisions:
► Memory
and caching is implemented to
keep the 3 strongest signals readily
available for position calculation.
► An SRAM lookup table stores individual
access point data including: MAC address, X
and Y coordinated, originating signal/noise
ratio.
► A queue stores 4 more recently acquired
signals, and allows for migration between
the top 3 signals and the queue.
Functionality:
► It
has the ability to write new map data into
the ~1K SRAM lookup table
► After acquiring at least 3 signals it will
output your current X and Y coordinates
► Has the ability to calculate the distance and
heading (angle) to a given location.
Major Functional Components:
► Top
3 / Queue module
Gives priority to the top 3 signals based on their
Signal-to-Noise Ratios
► Lookup
Table Module
Hard coded data of MAC addresses, x and y coordinates as
well as Signal-to-Noise Ratios (SNR).
► Calc
Module
Given the coordinates of 3 Access Points and their
distance, it will calculate the current position.
Top 3
Queue
Map
Data
FPU
Pre-Normalization/
Denormalization
Addition /
subtraction
Calc
Waypoint
- heading
- directions
Multiplication /
division
Post-normalization /
Denormalization
Trig
(arctan)
Top 3 module
SA3
SA1
SB1
SC1
+
+
+
SA2
SB2
SC2
+
SHR2
SA4
SB3
+
SHR2
SB4
MUX
Queue
ROW A
+
SHR2
SC4
MUX
Queue
SC3
MUX
Queue
ROW B
ROW C
Major Functional Components:
► Floating-point
unit (FPU)
 Performs the addition, subtraction,
multiplication and division of floating-point
numbers.
► Waypoint
Calculator
 Calculates distance and angle to requested
destination
 Relies on a trig lookup table
Underlying Assumptions:
► Map
data will be available for the current
location.
► An RF antenna with A/D converter will
provide a signal with data from wireless
access points.
► Access points will broadcast their MAC
address.
► The user will not be moving quickly and/or
moving out of map range.
Underlying Assumptions:
► The
available signal quality will allow for
good distance approximation.
► The power and location of the sending
signal is included in the map data.
► No more than 16 bits of floating point
precision are necessary for our calculations.
Calc Module: Triangulation Formula
assign dA = rsnoA/rsniA;
assign dB = rsnoB/rsniB;
assign dC = rsnoC/rsniC;
assign sqrt = q;
assign Xr1 = (-b+sqrt)/(2*a);
assign Xr2 = (-b-sqrt)/(2*a);
assign A = (dA-dB+rxB*rxBrxA*rxA)/(2*(ryB-ryA))+(ryB+ryA)/2;
assign B = (rxB-rxA)/(ryB-ryA);
assign a = a+B*B;
assign b = 2*(ryA*B-rxA-A*B);
assign c = rxA*rxA+ryA*ryA+A*A2*ryA*A-dA;
assign Yr1 = A - B*Xr1;
assign Yr2 = A - B*Xr2;
assign delta = b*b-4*a*c;
//square root function
q = 0;
y = 2;
for(i=0;i<14;i=i+1)
begin
q = delta/y;
y = (y+q)/2;
end
assign result1 = (Xr1-rxC)*(Xr1-rxC)+(Yr1-ryC)*(Yr1ryC)-dC;
assign result2 = (Xr2-rxC)*(Xr2-rxC)+(Yr2-ryC)*(Yr2ryC)-dC;
if(result1 < 0) assign result1 = -result1;
if(result2 < 0) assign result2 = -result2;
if(result1 < result2)
begin
assign xPos = $realtobits(Xr1);
assign yPos = $realtobits(Yr1);
end
else begin
assign xPos = $realtobits(Xr2);
assign yPos = $realtobits(Yr2);
end
Questions/Concerns
► Transistor
Count – Highly dependant on how
many transistors we need for floating point
calculations
► Speed – Will take >50 cycles to achieve a
position calculation.