Horizon Inquiries Against Portable Lightweight Gadgets in MANETs.


41 views
Uploaded on:
Category: People / Lifestyle
Description
A portable client is just keen on information of a restricted topographical range, however the inquiry includes information put away on different cell phones. Sample ...
Transcripts
Slide 1

Horizon Queries Against Mobile Lightweight Devices in MANETs Zhiyong Huang 1 Christian S. Jensen 2 Hua Lu 1 Beng Chin Ooi 1 National University of Singapore, Singapore 2 Aalborg University, Denmark

Slide 2

Outline Introduction Problem Definition Skyline Queries in MANETs Optimizations on Mobile Devices Experimental Studies Conclusion

Slide 3

Introduction Skyline inquiry Operator in view of predominance MANET Self-sorting out, remote versatile impromptu systems Physical environment of this work Lightweight gadgets

Slide 4

Skyline Queries in MANETs Assumptions Each asset obliged gadget holds a bit of the whole dataset Devices impart through MANET A portable client is just intrigued by information of a restricted land territory, however the question includes information put away on various cell phones

Slide 5

M 1 M 2 M 3 M 4 Example M 1 to M 4 hold distinctive inn relations M 2 is occupied with shabby and great inns inside the circle zone

Slide 6

Outline Introduction Problem Definition Skyline Queries in MANETs Optimizations on Mobile Devices Experimental Studies Conclusion and Future Work

Slide 7

Problem Setting MANET of m cell phones { M 1 , M 2 , … , m } Local connection R i on every gadget M i < x , y , p 1 , p 2 , … , p n > Skyline issued by a gadget M organization < id, pos organization , d > id : system id of inquiry originator M organization pos : position of M organization d :separation (from pos) of interest

Slide 8

Technical Challenges Slow and untrustworthy remote channels contrasted with wired associations With diminish information exchanged between gadgets Resource-compelled gadgets Storage and handling sparing methods on cell phones

Slide 9

Outline Introduction Problem Definition Skyline Queries in MANETs Optimizations on Mobile Devices Experimental Studies Conclusion

Slide 10

Straightforward Strategy Query originator M organization Executing a nearby horizon inquiry: SK organization Sends inquiry to other cell phones Merges comes about while accepting them A cell phone M i Executing a neighborhood horizon inquiry too Sends result SK i back to M organization Instead of sending entire R i

Slide 11

Discussion Final horizon result: SK ≠ U SK i , SK U SK i FSK = U SK i – SK FSK contains each one of those tuples that are not in SK but rather sent between gadgets Identify SK i –SK on gadget M i Inspiration of semi-join U |

Slide 12

Filtering Strategy Any tuple tp i in SK i –SK is ruled by some tuple(s) tp j in SK Where to discover such tp j s? Pick from M organization " s nearby result Send < id, pos organization , d, tp j > as question M i sift through tuples utilizing tp j Which one to pick? Overwhelming district

Slide 13

p 2 M a x c o r n e r o f d a t a s p a c e b 2 D o m i n a t i n g R e g i o n p j 2 t p j p 1 0 p b j 1 Dominating Region The capacity of tp j to command others Tuple esteem < p j1 , p j2 , … , p jn > Data space limits Volume of ruling locale VDR j = ∏ k ( b k - p jk ) Choose from SK organization tp flt with max VDR j Indep. dissemination

Slide 14

Dominating Ability Two lodging relations Price range (20..200) Smaller rating implies better (1..10) Relation R 1 Relation R 2 ( M organization )

Slide 15

Estimated Dominating Region Over-estimation VDR j = ∏ k ( max k - p jk ) max k :pre-indicated bigger quality Under-estimation VDR j = ∏ k ( h k - p jk ) h k :nearby greatest

Slide 16

Dynamic Filtering Tuples Three inn relations M 4 - > M 3 - > M 1 VDR 31 =980 VDR 41 =960 Relation R 3 Relation R 4 ( M organization ) Relation R 1

Slide 17

Query Log Mechanism To keep away from the same question more than once on any gadget M i Add a label cnt to inquiry issued by M organization < id, cnt, pos organization , d, tp flt > M i records/checks/redesigns < id, cnt > Processes and advances just cnt log <cnt cnt can be a byte to spare cost A gadget can issue 256 inquiries Reset following a period, say one day

Slide 18

Outline Introduction Problem Definition Skyline Queries in MANETs Optimizations on Mobile Devices Experimental Studies Conclusion

Slide 19

Dataset Storage Goals Space productive Local preparing effective Operations Spatial degree check Distinct directions Attribute esteem examination Floats Duplicates

Slide 20

Hybrid Storage Model Spatial facilitates Real values MBR i (x max , y max , x min , y min ) Attribute values Ascending areas IDs Sort p 1 Relation R i Sorted areas p 1 p n …

Slide 21

Local Skyline Computing Sptial check mindist ( pos organization , MBR i ) > d Skyline registering Comparison of IDs rather than genuine estimations of buoy sort p 2 to p n just Update separating tuple if vital Choose the one with bigger VDR esteem

Slide 22

Assembly on Query Originator When M organization gets SK i from others Duplication end False positive expelling A straightforward settled circle is sufficient Comparing arranges Identify copies Comparing trait values Identify false positive reports from both SK organization and SK i

Slide 23

Outline Introduction Problem Definition Skyline Queries in MANETs Optimizations on Mobile Devices Experimental Studies Conclusion

Slide 24

Experiment Parameters

Slide 25

Studies on Local Optimization HP iPAQ h6365 pocket PC MS Windows Mobile 2003 200MHz TI OMAP1510 processor 64MB SDRAM (55MB client open) SuperWaba Java-based open-source stage for PDA and cell phone applications www.superwaba.org

Slide 26

Time versus Local Cardinality Flat Storage versus Hybrid Storage Anti-Correlated versus Independent HS brings about less handling cost

Slide 27

Time versus Local Dimensionality Average of expenses on both conveyances Coz they are near each different HS still performs better

Slide 28

Performance in Simulation Simulated MANET JiST-SWANS A Jave based MANET test system http://jist.ece.cornell.edu/Pentium IV desktop PC MS Windows XP 2.99GHz CPU 1 GB memory

Slide 29

Settings Device setting Data apportioned and designated to gadgets utilizing a network of m 1/2 by m 1/2 1-5 inquiries for every gadget MANET settings Total reenactment time: 2 hours Speed range: 2 unit/s – 10 unit/s Holding time: 120 seconds Wireless steering convention: AODV

Slide 30

Data Reduction Efficiency Data Reduction Rate SK i " is the neighborhood horizon subsequent to sifting Pre-tests in static setting Forwarding question out recursively Findings No critical contrast between precise VDR and assessed VDRs Dynamic sifting is all the more capable

Slide 31

Data Reduction Rate

Slide 32

Response Time - BF Breadth-First question sending Parallel Time getting answers from 80% different gadgets Cannot guarantee all gadgets are constantly reachable and accessible in MANETs M 2 M 1 M 3 M organization M 5 M 4 Query message Result message

Slide 33

Response Time - DF Depth-First sending Serialized Query closes when originator discovers all neighbors have prepared the inquiry M 2 M 3 M 1 M 4 M 5 M organization Query message Result message

Slide 34

Response Time

Slide 35

Query Message Count Only cell phone number influences the question message tally clearly Better execution of BF is not free

Slide 36

Outline Introduction Problem Definition Skyline Queries in MANETs Optimizations on Mobile Devices Experimental Studies Conclusion

Slide 37

Conclusion Problem setting MANET of lightweight gadgets Skyline inquiries with spatial limitations Solution highlights Filtering based circulated inquiry preparing methodology to diminish correspondence cost Specialized nearby stockpiling and calculation to accelerate nearby preparing Experimentally confirmed execution

Slide 38

Q & A Thanks!

Recommended
View more...