Device discovery in a ubiquitous computing environment

Technologies are generally described for methods, instructions, and client applications for device discovery in a ubiquitous computing environment. In some examples, the methods, instructions, and client applications may facilitate the organization of features of devices in a ubiquitous computing environment into a series of hierarchical hash numbers, the ordering of the hierarchical hash numbers corresponding to the respective devices, and the searching for a particular one of the devices by attempting to match hashed search criteria to the ordered hierarchical hash numbers at one of the devices in the ubiquitous computing environment.

CROSS-REFERENCE TO RELATED APPLICATION

The present application is the U.S. national phase application of, and claims priority to, International application No. PCT/CN2010/079911, filed on Dec. 17, 2010, the entirety of which is incorporated herein by reference.

TECHNICAL FIELD

The implementations and embodiments described herein pertain generally to search in a ubiquitous computing environment.

BACKGROUND ART

A ubiquitous computing environment, particularly a peer-to-peer computing environment, employs a decentralized architecture by which tasks and resources are partitioned among network nodes. The network nodes, or peers, are both suppliers and consumers of resources, including data and storage. Further, in such an environment, resources are typically exchanged directly over the underlying Internet Protocol (alternatively referred to as “IP”).

Distributed hash tables (alternatively referred to as “DHTs”) are a class of decentralized distributed systems that provide a lookup service for resources in the peer-to-peer computing environment. DHT-based networks utilized for data discovery and management include the Chord project, PAST storage utility, the P-Grid, and the CoopNet content distribution system.

SUMMARY OF INVENTION

A client application implements methods and programs to facilitate the organization of features of devices in a decentralized computing environment into a series of hierarchical hash numbers, the ordering of the hierarchical hash numbers corresponding to the respective devices, and the searching for a particular one of the devices by attempting to match hashed search criteria to the ordered hierarchical hash numbers at one of the devices in the decentralized computing environment.

DESCRIPTION OF EMBODIMENTS

FIG. 1shows an example of a ubiquitous computing environment100in which device discovery may be implemented, in accordance with embodiments described herein.

Ubiquitous computing environment100may alternatively be regarded as a peer-to-peer network100since the embodiments of device discovery described herein are implemented within the context of a decentralized computing environment in which the peer nodes, or devices, act as both clients and servers to the other nodes in the computing environment.

Devices102(a),102(b),102(c),102(d),102(e), . . . ,102(n), which may be alternatively referred to as “devices102,” collectively, or “device102,” generically, are participating nodes on decentralized, peer-to-peer network100. Devices102may each be regarded as a communication endpoint or terminal equipment on peer-to-peer network100. Devices102may each further be regarded as an active electronic device that is capable of sending, receiving, or forwarding information over peer-to-peer network100. Examples of such active electronic devices include, but are not limited to, mobile (or cellular) telephones, desktop computers, laptop computers, tablet/slate computers, servers, modems, hubs, bridges, or printers/copiers. In accordance with at least some of the foregoing examples of devices102, ubiquitous computing environment100may alternatively be implemented as a wireless communications network.

As shown inFIG. 1, not all of devices102are directly communicatively connected to each other. Further, the population of peer-to-peer network100is dynamic; that is, not all of devices102remain in peer-to-peer network100. Rather, various ones of devices102(a),102(b),102(c),102(d),102(e), . . . ,102(n) may drop out of peer-to-peer network100, or one or more dynamic devices may be added to peer-to-peer network100; and the deletions and additions to peer-to-peer network100need not be symmetrical, proportional, or synchronous to each other.

As further shown inFIG. 1, each of devices102(a),102(b),102(c),102(d),102(e), . . . ,102(n) on peer-to-peer network100has residing thereat a corresponding client application104(a)-(n), which may be alternatively referred to as “applications104,” collectively, or “application104,” generically. Applications104, each of which further includes a respective figure table (which may be alternatively regarded or referred to as a “distribution table”), are the means by which device discovery is implemented in accordance with the embodiments described herein.

FIG. 2shows an example embodiment of client application104and corresponding interface200for device discovery in ubiquitous computing environment100.

In accordance with the embodiments of device discovery in a ubiquitous computing environment described herein, each of devices102(a),102(b),102(c),102(d),102(e), . . . ,102(n) on peer-to-peer network100may have a headword to describe the function of the respective device as well as one or more descriptive words, or attributes, to further describe the functionality or some other feature of the respective device. Non-limiting examples of such other features may include a device brand, model, functionality, or even geographic location.

Further, each of devices102(a),102(b),102(c),102(d),102(e), . . . ,102(n) may have a resident instance of client application104, on which interactive interface200and figure table250may reside. Interface200may include function data field205, into which a user of the respective one of devices102may enter or specify a function, e.g., “printer,” of a particular device that is sought on peer-to-peer network100. Interface200may further include data fields210(a),210(b),210(c), . . . ,210(n), which may be alternatively referred to as, collectively, “attribute data fields210,” into which the user of the respective one of devices102may enter or specify further attributes of the device sought on peer-to-peer network100. It should be noted that the attributes of respective ones of devices102may alternatively be entered into attribute data fields210automatically without user intervention such as when a respective device102is connected to peer-to-peer network100. It is by the function data field205and attribute data fields210(a)-210(n) that devices102, and even search criteria for a particular one of devices102, may be organized, i.e., classified, for the various embodiments of device discovery.

Thus, if the sought-after device is a printer, the functional attribute entered into function data field205may be entered or specified as “printer,” and then pre-configured attribute data fields210may receive attributes that are further descriptive of the functionality and other features of the sought-after printer. Non-limiting examples of such further descriptions, with respect to “printer” entered or specified to data field205, may include “Toshiba,” “650C,” “laser,” “color,” or “second floor.” As set forth above, attribute data fields210(a)-210(n) may be pre-configured to receive attribute data that may include, e.g., a device brand, model, functionality, or location. The pre-configuration that determines into which particular one of attribute data fields210the respective attribute data is to be entered or specified may be dynamic, and may differ from one embodiment to another. In addition, attribute data fields210may be uniquely pre-configured for specific types of devices, which may be identified by the entry to function data field205. Therefore, using the attributes provided above as a non-limiting example, “Toshiba” may be entered or otherwise specified to attribute data field210(a), “650C” may be entered or otherwise specified to attribute data field210(b), “laser” may be entered or otherwise specified to attribute data field210(c), “color” may be entered or otherwise specified to attribute data field210(d), and “second floor” may be entered or otherwise specified to attribute data field210(g).

Accordingly, using the above example as context, not all of attribute data fields210are required to be filled to correspond to an entry to function data field205since, for example, not all of the attributes of the sought-after device are known to the user of the current one of devices102. In the above example, there are no entries to attribute data fields210(e),210(f), or those after attribute data field210(g). When a particular attribute is not known to the user of the current one of devices102, the pre-configured one of data fields210that is to receive that particular attribute may be filled with “none,” “null,” or some variant thereof to indicate that the corresponding attribute has no value.Upon receiving data entries to function data field205and at least one of attribute data fields210(a)-210(n), client application104on a respective one of devices102may hash the data entries, resulting in a cumulative search hash number (SHN).

More particularly, in some embodiments of client application104, a base hash function, e.g., SHA−1, may be utilized to separately map each of function data field205and attribute data fields210(a)-210(n) to a corresponding hash value of length M in hash data field215and hash data fields220(a)-220(n), the latter of which may alternatively be referred to, collectively, as “hash data fields220.” Thus, the hash value of the entry to function data field205may be mapped to hash data field215; and the hash values of the entries to attribute data fields210(a)-210(n) may be mapped, respectively, to hash data fields220(a)-220(n). For those attribute data fields210(a)-210(n) having a value of “none,” “null,” or some variant thereof, the corresponding one of hash data fields220(a)-220(n) may be populated with the value zero.

It is noted that other base hash functions may be utilized in various embodiments of device discovery, and therefore citing the example of SHA−1 is not intended to be limiting in any manner.

Hash data fields215and220(a)-220(n) may be concatenated, and thus be regarded as the aforementioned cumulative search hash number (SHN). SHN is the measure, or criteria, for comparison to the contents of figure table250resulting in device discovery. The contents of figure table250includes, at least, cumulative device hash numbers (DHN) for at least a portion of devices102on peer-to-peer network100.

FIG. 3shows example table, i.e., figure table or distribution table,250utilized in various embodiments of device discovery in ubiquitous computing environment100.

Table250may store at least DHN and IP addresses of a predetermined number of devices102on peer-to-peer network100. More particularly, with peer-to-peer network100being populated with N number of devices or nodes, and because figure table250is distributed, each of devices102may resolve the base hash function by communicating with only a portion of the N−1 other devices102on peer-to-peer network100. Thus, in steady state, each instance of figure table250maintains DHN and IP addresses for approximately only 0(log N) other devices.

More particularly, DHN for any one of devices102(a),102(b),102(c),102(d),102(e)102(n) on peer-to-peer network100may be determined in the same manner as SHN is determined for a device that is sought-after by the user of one of devices102. That is, the function data, i.e., headword, and available attribute data for a particular one of devices102may be entered in the corresponding one of pre-configured data fields205and210(a)-210(n), and may then be individually hashed to corresponding hash values in fields similar to hash data fields215and220(a)-220(n). The resulting hash data fields215and220(a)-220(n) may then be concatenated and entered to figure table250in the same format as SHN.

Thus, figure table250may include further columns that depict at least DHN for, e.g., 0(log N), or other devices102on peer-to-peer network100. More particularly, in addition to storing SHN, table250may store at least DHN and IP address for one or more of devices102, and may serve as the platform for a search for a particular one of devices102(a),102(b),102(c),102(d),102(e), . . . ,102(n) on peer-to-peer network100.

As set forth above, substantially all of devices102on peer-to-peer network100may include an instance of client application104residing thereon. Each instance of client application104may, in turn, have an instance of interface200and an instance of figure table250included therein. However, as set forth above, not all instances of figure table250have DHN for every one of devices102on peer-to-peer network100. For example, figure table250shown in the example ofFIG. 3includes SHN and DHN for devices102(a),102(b),102(d),102(e), and various ones of devices through102(n). Clearly missing is DHN for device102(c), though DHN of others of devices through102(n) may also be missing from figure table250.

Further, as set forth above, for those attribute data fields210(a)-210(n) having a value of “none,” “null,” or some variant thereof, the corresponding one of hash data fields220(a)-220(n) may be populated with the value zero. Those of hash data fields220(a)-220(n−1) having the value zero that precede the last one of hash data fields220with a non-zero value may be referred to as, e.g., “empty pre-attribute data fields;” and those of hash data fields220(b)-220(n) having the value zero that follow the last one of hash data fields220with a non-zero value may be referred to as, e.g., “empty post-attribute data fields.”

Accordingly, when populating figure table250, empty pre-attribute data fields may maintain the value zero while empty post-attribute data fields may be filled with the value 2M−1, with “M,” again, referring to the length of the hash values in each of hash data fields220. Of course, alternative embodiments may reverse the initial assignment of values to empty pre-attribute data fields and empty post-attribute data fields. But the description of the present embodiment will maintain that empty pre-attribute data fields have the value zero and empty post-attribute data fields have the value 2M−1. This aspect of the configuration of figure table250will be described below with reference to the search for a particular one of devices102on peer-to-peer network100in connection with the description ofFIG. 4.

FIG. 4shows a sample processing flow400for various embodiments of device discovery in ubiquitous computing environment100. Sample processing flow400is described below referencing features described with regard to the non-limiting examples ofFIGS. 1-3. The order in which the operations are described in the sample processing flow is not intended to be construed as a limitation, and any number of the described blocks may be combined in any order and/or in parallel to implement each process. Moreover, the blocks in theFIG. 4may be operations that can be implemented in hardware, software, or a combination thereof. In the context of software, the blocks represent computer-executable instructions that, when executed by one or more processors, cause one or more processors to perform the recited operations. Generally, computer-executable instructions include routines, programs, objects, components, data structures, and the like that cause the particular functions to be performed or particular abstract data types to be implemented.

Furthermore, as set forth above, the example embodiments described in this detailed description, drawings, and claims are not meant to be limiting. Other embodiments may be utilized, and other changes may be made, without departing from the spirit or scope of the subject matter presented herein. Therefore, the description ofFIG. 4will refer to “distribution table250,” in view of the earlier disclosure that each instance of application104may include an instance of figure table250, which may be alternatively be regarded or referred to as “distribution table”250.

Block402refers to the organizing of DHN and, in accordance with at least some embodiments of device discovery, SHN. Block402includes Block404and Block406.

Block404(Organize Features of Devices(s)) more particularly refers to the organizing of features of at least a subset of devices102on peer-to-peer network100, which may be implemented at the respective one of devices102on which the particular instance of client application104resides or, alternatively, at others of devices102. In the former scenario, function data and attribute data of the predetermined number of other devices102may be received by client application104in preconfigured data fields205and210(a)-210(n). In the latter scenario, function data and attribute data of respective other devices102may be organized by preconfigured data fields205and210(a)-210(n) in the respective instance of client application104at respective device102. Processing may continue from block404to block406.

Block406(Hash Attributes of Device(s)) refers to functional data and attribute data of respective devices102being hashed.

Subsequent to the first scenario at block404, block406may include hashing, respectively, entries to function data field205and entries to attribute data fields210(a)-210(n) of the predetermined number of other devices102. Hash data fields215and220(a)-220(n), the value of each having length M, may be concatenated to form DHN for respective other devices102.

Subsequent to the second scenario at block404, block406may include hashing function data and attribute data of the predetermined number of other devices102. Hash data fields215and220(a)-220(n) may be concatenated to form DHN for respective devices102, which may then be transmitted to the instance of client application104to which the respective devices102communicate. Processing may continue from block406to block408.

Block408(Order Hash Numbers for Device(s)) refers to organizing and/or ordering the DHN of the respective other devices102into an instance of distribution table250. The ordering of DHN for respective other devices102may be implemented in a hierarchical manner, by which DHN are stored in distribution table250sequentially, i.e., in accordance with ascending or descending hash values. Alternatively, the ordering of DHN of respective devices102at distribution table250may be implemented in accordance with various other criteria, e.g., in accordance with frequency by which the particular device is sought-after by others of devices102, in accordance with proximity with device102on which the particular instance of client application104resides, etc. Processing may continue from block408to block410.

Block410(Search for Particular Device(s)) refers to implementing a search for any particular one of devices102on peer-to-peer, i.e., ubiquitous, network100.

SHN that is the basis, or criteria, for the search may be organized by entering the functional attribute of a sought-after device into function data field205and then entering attributes that further describe the sought device into the appropriate ones of pre-configured attribute data fields210(a)-210(n). Once again, attribute data fields210(a)-210(n) may be pre-configured to receive attribute data that may include, as non-limiting examples, a device brand, model, functionality, or location. Further, the pre-configuration that determines into which particular attribute data field210the respective attribute data is to be entered may be dynamic, and may differ from one embodiment to another; and attribute data fields210may be uniquely pre-configured for specific types of devices.

Further, when implementing the operation at block410, not all of attribute data fields210will necessarily be filled for each entry to function data field205. In the event that a particular attribute of the sought device is not known, the pre-configured one of attribute data fields210that is to receive that particular attribute may be filled with “none,” “null,” or a variant thereof to indicate that the corresponding attribute has no value.

Upon receiving data entries to function data field205and at least one of attribute data fields210(a)-210(n), client application104on a respective one of devices102may implement a base hash function on the data entries, resulting in cumulative SHN. That is, each of function data field205and attribute data fields210(a)-210(n) may be mapped to a corresponding hash value in hash fields215and220(a)-220(n). As with DHN that populate distribution table250, empty pre-attribute data fields may maintain the value zero, and empty post-attribute data fields may include the value 2M−1.

The search at block410may then include an attempt to match SHN to DHN that populate distribution table250. If there is an exact match between the SHN and one of the aforementioned DHN, a notification of the result is made on the device102on which the particular instance of client application104resides.

If there is no exact match between SHN and one of the aforementioned DHN, the search continues for DHN that most closely matches SHN. Alternative embodiments of device discovery may contemplate the closest match between a non-matching DHN and SHN as being DHN that most closely matches the SHN without exceeding the value of SHN, or may contemplate the closest DHN match being the closest DHN value that exceeds the value of SHN.

Further, attempts to find the closest match between DHN that populate distribution table250and SHN may include filling empty pre-attribute data fields with corresponding values of the device102at which the particular instance of client application104resides. Of course, if alternative embodiments initially populated distribution table250with empty pre-attribute data fields having the value 2M−1 and empty post-attribute data fields having the value zero, the current action would include empty post-attribute data fields being filled with the corresponding values of the current device102.

As set forth above, not all of devices102are directly communicatively connected to each other. Further, the population of peer-to-peer network100may be dynamic. Therefore, transferring the search for a match for SHN to another device broadens the search to more of devices102populating peer-to-peer network102.

At least one embodiment of device discovery may result in the search operation ceasing if an exact match between SHN and any of DHN populating the table250is not found. Other alternative embodiments of device discovery may result in the search operation continuing by having SHN transmitted or otherwise transferred to another one of devices102to be compared to DHN populating distribution table250on the instance of client application104at that other one of devices102. Process400may then be repeated thereat, with DHN of those of devices102communicating with that other device102populating the other distribution table250. Client application104may be configured to terminate a search after a predetermined number of iterations if an exact match with a particular SHN is not found on that predetermined number of devices102.

In accordance with the above description, device discovery in a peer-to-peer, i.e., ubiquitous, computing environment may be implemented using a base hash function.

FIG. 5shows sample computing device500in which various embodiments of device discovery in a ubiquitous computing environment may be implemented. More particularly,FIG. 5shows an illustrative computing embodiment, in which any of the operations, processes, etc. described herein may be implemented as computer-readable instructions stored on a computer-readable medium. The computer-readable instructions may, for example, be executed by a processor of a mobile unit, a network element, and/or any other computing device.

In a very basic configuration502, computing device500typically includes one or more processors504and a system memory506. A memory bus508may be used for communicating between processor504and system memory506.

Depending on the desired configuration, processor504may be of any type including but not limited to a microprocessor (μP), a microcontroller (μC), a digital signal processor (DSP), or any combination thereof. Processor504may include one more levels of caching, such as level one cache510and level two cache512, processor core514, and registers516. An example processor core514may include an arithmetic logic unit (ALU), a floating point unit (FPU), a digital signal processing core (DSP Core), or any combination thereof. An example memory controller518may also be used with processor504, or in some implementations memory controller518may be an internal part of processor504.

Depending on the desired configuration, system memory506may be of any type including but not limited to volatile memory (such as RAM), non-volatile memory (such as ROM, flash memory, etc.) or any combination thereof. System memory506may include an operating system520, one or more applications522, and program data524.

Application522may include Client Application104that is arranged to perform the functions as described herein including those described previously with respect toFIGS. 1-4. Program data524may include Table250, which may alternatively be referred to as “figure table250” or “distribution table250,” which may be useful for implementing device discovery as described herein.

Computing device500may have additional features or functionality, and additional interfaces to facilitate communications between basic configuration502and any required devices and interfaces. For example, bus/interface controller530may be used to facilitate communications between basic configuration502and one or more data storage devices532via storage interface bus534. Data storage devices532may be removable storage devices536, non-removable storage devices538, or a combination thereof. Examples of removable storage and non-removable storage devices include magnetic disk devices such as flexible disk drives and hard-disk drives (HDD), optical disk drives such as compact disk (CD) drives or digital versatile disk (DVD) drives, solid state drives (SSD), and tape drives to name a few. Example computer storage media may include volatile and nonvolatile, removable and non-removable media implemented in any method or technology for storage of information, such as computer readable instructions, data structures, program modules, or other data.

Computing device500may also include interface bus540for facilitating communication from various interface devices, e.g., output devices542, peripheral interfaces544, and communication devices546, to basic configuration502via bus/interface controller530. Example output devices542may include graphics processing unit548and audio processing unit550, which may be configured to communicate to various external devices such as a display or speakers via one or more A/V ports552. Example peripheral interfaces544may include serial interface controller554or parallel interface controller556, which may be configured to communicate with external devices such as input devices (e.g., keyboard, mouse, pen, voice input device, touch input device, etc.) or other peripheral devices (e.g., printer, scanner, etc.) via one or more I/O ports458. An example communication device546may include network controller560, which may be arranged to facilitate communications with one or more other computing devices562over a network communication link via one or more communication ports564.

CITATION LIST